Create a balanced Binary Search Tree from a sorted array

Given a sorted integer array of length n, create a balanced Binary Search Tree using elements of the array.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

A BST is balanced if:
Height of left subtree and right subtree of root differ by at most 1. Left and right subtrees are subtrees is balanced.

Algorithm:
1. Initialize start = 0, end = length of the array - 1
2. Set mid = (start+end)/2
3. Create a tree node with mid as root (lets call it A).
4. Recursively do following steps:
   a). Calculate mid of left subarray and make it root of left subtree of A.
   b). Calculate mid of right subarray and make it root of right subtree of A.


Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Create a balanced Binary Search Tree (BST) from a sorted array</b><br>
 * Given a sorted integer array of length n, create a balanced Binary Search Tree using the values of the array. <br><br>
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=VCTP81Ij-EM">Sorted array to balanced bst - Youtube Link</a> 
 * @author Saurabh
 *
 */
public class SortedArrayToBalancedBST {

	public static void main(String[] args) {
		int array[] = { 3, 6, 8, 23, 48, 76, 89 };
		TreeNode treeRoot = createBST(array);
		inorder(treeRoot);
	}
	
	public static TreeNode createBST(int array[]) {

		return createBST(array, 0, array.length-1);
	}

	private static TreeNode createBST(int[] array, int start, int end) {
		
		if(array == null || array.length == 0 || start > end) {
			return null;
		}
		
		int mid = (start + end)/2;
		TreeNode root = new TreeNode(array[mid]);
		
		root.setLeft(createBST(array, start, mid-1));
		root.setRight(createBST(array, mid+1, end));
		
		return root;
	}
	
	public static void inorder(TreeNode root) {
		if(root == null) {
			return;
		}
		
		inorder(root.getLeft());
		System.out.print(root.getData() + "  ");
		inorder(root.getRight());
	}
}

class TreeNode {


	private int data;
	private TreeNode left;
	private TreeNode right;
	
	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}

	public TreeNode(int data) {
		super();
		this.data = data;
	}

}
		

Order of the Algorithm

Time Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer