Convert Sorted Array to Balanced Binary Search Tree (BST)

November 25, 2010 in binary tree, divide and conquer

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.


If you are having hard time in understanding my previous post: Largest Binary Search Tree (BST) in a binary tree, do not fret as that problem is a comparably trickier tree problem for an interview session. But that should not be an excuse for you to not improve your ability to think recursively (without your brain stack being overflowed of course ).

Recursion is a very powerful problem-solving mechanism, and you would not go very far without it during an interview session. Here might be an easier tree problem for you to start before you hop on those challenging ones.

Hint:
This question is highly recursive in nature. Think of how binary search works.

An example of a height-balanced tree. A height-balanced tree is a tree whose subtrees differ in height by no more than one and the subtrees are height-balanced, too.

Solution:
If you would have to choose an array element to be the root of a balanced BST, which element would you pick? The root of a balanced BST should be the middle element from the sorted array.

You would pick the middle element from the sorted array in each iteration. You then create a node in the tree initialized with this element. After the element is chosen, what is left? Could you identify the sub-problems within the problem?

There are two arrays left — The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node’s left and right child.

The code below creates a balanced BST from the sorted array in O(N) time (N is the number of elements in the array). Compare how similar the code is to a binary search algorithm. Both are using the divide and conquer methodology.

Further Thoughts:

Consider changing the problem statement to “Converting a singly linked list to a balanced BST”. How would your implementation change from the above?

Check out my next post: Convert Sorted List to Balanced Binary Search Tree (BST) for the best solution.

VN:F [1.9.22_1171]
Rating: 4.4/5 (47 votes cast)
Convert Sorted Array to Balanced Binary Search Tree (BST), 4.4 out of 5 based on 47 ratings

25 responses to Convert Sorted Array to Balanced Binary Search Tree (BST)

  1. Nice post.
    Happy Thanksgiving.

    VA:F [1.9.22_1171]
    +3
  2. I'm having trouble thinking of an approach to the linked list case.. any hints/tips ?

    VA:F [1.9.22_1171]
    0
  3. The hint is to modify the above solution for the linked list case (It is actually few lines of code changes for the linked list case).

    A naive solution would be O(N lg N). The biggest challenge is linked list does not permit random access in O(1). Could you try to insert the node by the list's order?

    VA:F [1.9.22_1171]
    0
  4. This still does not produce a balanced tree.

    VA:F [1.9.22_1171]
    0
  5. Please Check Your Program it Not Seems to be correct , i have check your program & m getting difficulty or might be i am not getting it please rewrite it with simple example say we have sorted array 1,2,3,4,5 so please show me output how constructed BST looks like..please try to give program..asap..thanks in advance..

    VA:F [1.9.22_1171]
    0
  6. Please Check Your Program it Not Seems to be correct , i have check your program & m getting difficulty or might be i am not getting it please rewrite it with simple example say we have sorted array 1,2,3,4,5 so please show me output how constructed BST looks like..please try to give program..asap..thanks in advance..

    Please Reply ASAP

    VA:F [1.9.22_1171]
    +1
  7. I think the solution is write. For sorted array 1, 2, 3, 4, 5, the result is
    3
    / \
    1 4
    \ \
    2 5

    VA:F [1.9.22_1171]
    -1
  8. GREAT IDEA!
    This helped me alot to make a cool balanced deep copy of my BST

    VA:F [1.9.22_1171]
    0
  9. m said on May 17, 2011

    Hey,

    You have a brilliant site! The problems are very interesting, and your explanations are great. :)

    About this one:
    It doesn’t seem to handle duplicates in the array (am i mistaken?). I think it be solved without breaking the O(n) guarantee as follows:
    before making the recursive calls,

    Then the recursive calls should be for

    and

    .

    Does that seem right? i may have missed some boundary conditions somewhere, sorry :)

    cheers,

    ..m

    VA:F [1.9.22_1171]
    0
  10. Hi, can some one help me wid this,

    Form a labelled binary tree of message “ROAD IS GOOD”.

    and mail me its answer..to my mail id-
    sauryanjan@gmail.com

    VA:F [1.9.22_1171]
    0
  11. “The code below creates a balanced BST from the sorted array in O(N) time”,why not O(lgN)?

    VN:F [1.9.22_1171]
    0
  12. This program doesn’t work for size =1

    VA:F [1.9.22_1171]
    0
  13. hi, if i want to add the parent address – is it possible ?
    the code does not add the parent address, only the left and right sons. thanks!

    VA:F [1.9.22_1171]
    0
    • just change the signature adding an extra ‘parent’ param:

      Hope it helps !

      VA:F [1.9.22_1171]
      0
  14. A more interesting problem would be to inplace convert the sorted Arr into BST array representation. Assume the array is extended till the (next power of 2)-1 or something like that.

    VA:F [1.9.22_1171]
    0
  15. hey, thanks for the articale.
    What is the best way to make the BST to red-black tree?
    The purpose is to build a red black tree in O(n) from sorted array.
    Thanks.

    VA:F [1.9.22_1171]
    0
  16. I think it is not O(N) it should be O(NlogN)

    VA:F [1.9.22_1171]
    -1
  17. No need to worry about overflow:

    Both (start+end)/2 and start + (end-start) / 2 always give you the same result

    VN:F [1.9.22_1171]
    0
    • It can cause overflow. Assuming the maximum integer PC can operate is 10, and start = 5, end = 6. If we use (start+end)/2, we will have overflow when doing start+end. But there will be no such problem when doing start+(end-start)/2.

      VN:F [1.9.22_1171]
      0
  18. Take the middle element of the input array and mark it as the root.
    Build up left and right sub trees recursively with the left and right sub array of the array.
    Return the tree.

    For explanation and code http://www.algoqueue.com/algoqueue/default/view/8847360/sorted-array-to-binary-search-tree

    VA:F [1.9.22_1171]
    0
  19. Thanks!! Very Nice Post..!!!!

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

2 trackbacks