Objective: Given a sorted array with unique elements, Create a binary search tree with minimal height.
Minimum height means we have to balance the number of nodes in both sides, as our input array is sorted and contains distinct integers, we could use that to construct our binary search tree in O(n) Time.
Why minimal height is important :
We can do the linear scan to the array and make the first element as root and insert all other elements into the tree but in that case tree will be skewed , which means all the nodes of the tree will be on the one side of the root so the height of the tree will be equal to the number of elements in the array. So here our objective is to keep the tree balanced as much as possible.
What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one.
Input: A one dimensional array
Output: Binary Search Tree of Minimal Height
 |
| Sorrted Array To BST Example |
Approach Recursion:
- Get the middle of the array
- make it as root. (By doing this we will ensure that half of the elements of array will be on the left side of the root and half on the right side.)
- Take the left half of the array, call recursively and add it to root.left.
- Take the right half of the array, call recursively and add it to root.right.
- return root.
Our Recursion base case is, if our start index is greater than end index, we can return Null, else we find the middle value and create a new BST node with that middle value.
Now, call the same method with (start to middle-1) in left side and (middle+1 to end) in right side.
Finally we can return our constructed BST.
Output:
Tree Display :
2 3 6 7 8 9 12 15 16 18 20
0 Comments