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.

No code, just psuedocode + Description

Solution

1) stack data structure is used for iterative post-order tree traversal.

The idea is to move down to leftmost node using left pointer. While moving down, push root and root’s right child to stack. Once we reach leftmost node, print it if it doesn’t have a right child. If it has a right child, then change root so that the right child is processed before.

Algorithm

2)DFS uses stack

In depth-first search the idea is to travel as deep as possible from neighbour to neighbour before backtracking. What determines how deep is possible is that you must follow edges, and you don\'t visit any vertex twice.

pseudocode:

BFS uses queue

BFS starting from vertex v:

create a queue Q

mark v as visited and put v into Q

while Q is non-empty

remove the head u of Q

mark and enqueue all (unvisited)

neighbours of u