Palantir Technologies

  www.palantir.com
  www.palantir.com
Work in HR? Unlock Free Profile

Interview Question

Business Development Engineer Interview Palo Alto, CA

Do a postorder binary tree traversal with constant memory

  (no stacks).
Answer

Interview Answer

2 Answers

0

Traverse the binary tree iteratively. Keep track of the nodes which have been visited.

Interview Candidate on Mar 18, 2012
0

I can't see this being possible without destroying the tree. My solution:
Right rotate at the root until the root has no left child. When this occurs, you go to its right child and either rotate until that position has no left child, or print it if it has no left child.
break out of both loops when there are no children
while(root has any children)
...while(root has left children)
......rotate root right
......new root = old root's parent
...print root
...new root = old root's right child

Jake S on Jul 5, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up