1 What data structure will you use for iterative postorder t

1) What data structure will you use for iterative post-order tree traversal? Explain how.

2) Given a binary tree (not necessarily a BST), return all root-to-leaf paths. Explain two solutions: one using stack, another one using queue.

3) Given a BST and a range [a, b], count how many elements are inside that range.

4) Given a binary tree, find Lowest Common Ancestor (LCA) of two nodes a and b.

Solution

Answer 1:

Stack is best suitable for iterative post order tree traversal. The postorder traversal can easily be done using two stacks though. The idea is to push reverse postorder traversal to a stack. Once we have reverse postorder traversal in a stack, we can just pop all items one by one from the stack and print them, this order of printing will be in postorder because of LIFO property of stacks.

Algorithm:
1. Push root to first stack.
2. Loop while first stack is not empty
Pop a node from first stack and push it to second stack
Push left and right children of the popped node to first stack
3. Print contents of second stack