🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will address a common problem in data structures: converting a sorted array into a height-balanced Binary Search Tree (BST). This problem is a good exercise in understanding how binary trees and binary search can be implemented in Java.
Problem
Given an array where elements are sorted in ascending order, convert it to a height-balanced BST, which is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.
Example:
Given the sorted array [1, 2, 3, 4, 5, 6]
One possible answer is:
4
/ \
2 5
/ \ \
1 3 6
2. Solution Steps
1. The basic idea is to find the middle element of the array and make it the root of the BST.
2. The left half of the array will form the left subtree, and the right half will form the right subtree.
3. Recursively apply this process to the left and right halves of the array.
4. Continue this process until the entire array is converted into a height-balanced BST.
3. Code Program
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
TreeNode root = sortedArrayToBST(nums);
printInOrder(root);
}
// Method to convert sorted array to BST
public static TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null; // Base case for empty array
return constructBSTRecursive(nums, 0, nums.length - 1); // Construct BST recursively
}
// Helper method to construct BST
private static TreeNode constructBSTRecursive(int[] nums, int left, int right) {
if (left > right) return null; // Base case
int mid = left + (right - left) / 2; // Middle element of the array
TreeNode node = new TreeNode(nums[mid]); // Create a node with the middle element
// Construct the left and right subtrees recursively
node.left = constructBSTRecursive(nums, left, mid - 1);
node.right = constructBSTRecursive(nums, mid + 1, right);
return node; // Return the root node of the BST
}
// Method for in-order traversal of the BST
public static void printInOrder(TreeNode node) {
if (node == null) return; // Base case
printInOrder(node.left); // Visit left subtree
System.out.print(node.val + " "); // Print node value
printInOrder(node.right); // Visit right subtree
}
}
Output:
1 2 3 4 5 6
Explanation:
The sorted array [1, 2, 3, 4, 5, 6] is converted into a height-balanced BST. The middle element (4) becomes the root, [1, 2, 3] forms the left subtree, and [5, 6] forms the right subtree. The sortedArrayToBST function recursively constructs the BST and the printInOrder function prints the BST in an in-order traversal, which outputs the elements in the original sorted order.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment