Make delicious recipes!

Convert doubly linked list to balanced BST in O(n)

If it were a sorted array, then converting to BST is easy.

Just make middle of array as root and recurse for left and right array halves.

Each recursive call returns left and right subtrees which should be current node’s children.

For a linked list, this is little difficult because we have to move to middle of current sublist, which takes n/2, n/4 and so on steps in each recursion. So a naive approach would become O(nlogn) approach.

To make it O(n), we use recursion again, so that left subtree constructs first exhausting the first half of the list. When left recursion ends, the list is moved to the middle (because its a global variable) and we can use it to create a new root.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal