Amazon Interview Question: Print an in-order binary tree... | Glassdoor

Interview Question

Software Technical Lead Interview

Print an in-order binary tree without using recursion.


Interview Answer

1 Answer


Use a stack to keep track of the what children to visit next and traverse depth first to the left most node. It's a little tricky because you want to visit nodes in R -> P -> L order so when you push nodes to the stack push them in Left Child, Parent, Right Child order; then when you've reached the left most node, popping the stack will return you to the parent node, popping the stack again will take you to the right child at which point you can iteratively add any children and continue. If there are no children of the right child then popping the stack will take you to the parent of the parent and so on.

Mailman on Jun 8, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.