Sorted Array to Balanced Binary Search Tree without recursion

Question

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?

Please state which language you are working with, and add a tag for that language. — Arif Burhan
– Arif Burhan, Commented Mar 30, 2016 at 0:33
Recursions can always be transformed to a loop with help of a stack. — HenryLee
– HenryLee, Commented Mar 30, 2016 at 2:41
@AndrewMyers this question is a poor fit for Programmers - it would be quickly voted down and closed over there, see Why do interview questions make poor Programmers.SE questions? Recommended reading: What goes on Programmers.SE? A guide for Stack Overflow — gnat
– gnat, Commented Mar 30, 2016 at 7:38

comingstorm · Accepted Answer · 2016-03-30 00:41:55Z

2

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...

edited Mar 30, 2016 at 0:41

answered Mar 30, 2016 at 0:35

comingstorm

26.2k3 gold badges47 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Sorted Array to Balanced Binary Search Tree without recursion

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related