CODEWITHSUNDEEP
javaarraysalgorithmrecursionbinary-search-tree
Nipun Ahuja
Nipun Ahuja

Reputation: 39

Sorted Array to Balanced Binary Search Tree without recursion

I was asked a question in an interview to construct a balanced binary search tree from a sorted array with recursion and without recursion. I was able to come up with a solution using recursion but failed to come up with a solution without recursion. Can anyone provide a solution to this problem without using recursion?

Upvotes: 1

Views: 1137

Answers (1)

comingstorm
comingstorm

Reputation: 26097

You can create and use your own stack (e.g., as an array or a linked list) and access it from inside a loop.

Each cell in the array or list will need to store the essential information about your tree that would otherwise be maintained by the recursive functions.

Some information from your recursive version (such as a depth counter) may be handleable by local variables instead. For some problems, you may be able to move all such information out of your stack into local variables; in such cases, you don't need an explicit stack at all...

Upvotes: 2

Related Questions