Palantir Technologies Interview Question: Do a postorder binary tree tr... | Glassdoor

Find your next job here

Interview Question

Business Development Engineer Interview Palo Alto, CA

Do a postorder binary tree traversal with constant memory

  (no stacks).

Interview Answer

2 Answers


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

Interview Candidate on Mar 18, 2012

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 root = old root's parent
...print root root = old root's right child

Jake S on Jul 5, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.