Interview Question

Software Engineer Interview

Do an in-order BST walk without additional data structures

  and without recursion.
Answer

Interview Answer

3 Answers

0

How is this possible? There needs to be some method to reach the previous node, recursion does it through stack frames, queues/stacks will do the same thing by storing the previous nodes.

The only other way is to modify the BST to include the parent node in the structure, apart from the 2 child nodes

R on Aug 27, 2014
0

I'm guessing the parent links are supposed to be there, even though normally a BST wouldn't have such a link, since it says "walk". That said, here's an awkward way I came up with to do it without "parent" links, but it's not really a walk any more.

Start by considering this problem: print all the nodes at depth=n (where n is the max depth) of a BST using iteration, no recursion, no other data structures.

To do this, one way is to count from i=0...2^n-1, and for each number, treat it as a set of instructions, written in binary, for how to traverse the tree, where zeros are "Left" and 1's are "Right", written in as many binary digits as the dept of the tree. So for depth=5, 0 is 00000 = Left, Left, Left, Left, Left, if the node is there, print it. when i = 7 it's 00111, Left Left Right Left Right, gets you the 7th node at level 5.

So for the problem above, now we just need to a way to print the "intermediate" number. After printing node i at level n, but before printing node i+1, you need to print ONE of the parent nodes. Which one? the lowest common parent of i and i+1. you can find this by doing i XAND i+1 to get a mask for the instructions for that, so if i = 5 and i+1 = 6, that's 00101 XAND 00110, the mask is 11100, so you need to do 001, left left right, to access the lowest parent node.

lastly, you need to know to depth of the tree for any of this to work, but this is trivial given the above: do the "access leaves at level n" algorithm, but just to check if they exist. when you hit a level where there's no nodes, you know the depth of the tree.

runtime is going to be n log(n), but i doubt there's a O(n) way to do it without parent links.

Ben on Oct 29, 2014
0

I'd use a stack but I guess that goes against using additional data structures.

A on Mar 13, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.