Trees

Question 1

InOrder(root) visits nodes in what order?

          _2_
        /         \
       20        5
       / \         / \
   22  40  25  15

Answer 1

22, 20, 40, 2, 25, 5, 15
InOrder Algorithm:
- Traverse Left, InOrder(left)
- Visit Root
- Traverse Right, InOrder(right)

In in-order we visit left -> root -> right

Question 2

PreOrderTraversal(root) visits nodes in what order?

          _2_
        /         \
       20        5
       / \         / \
   22  40  25  15

Answer 2

2, 20, 22, 40, 5, 25, 15
PreOrder Algorithm:
- Visit Root
- Traverse Left, PreOrder(left)
- Traverse Right, PreOrder(right)

In pre-order, we visit the root first
- root => left => right

Question 3

PostOrderTraversal(root) visits nodes in what order?

          _2_
        /         \
       20        5
       / \         / \
   22  40  25  15

Answer 3

22, 40, 20, 25, 15, 5, 2

PostOrder Algorithm:

• Traverse Left, PreOrder(left)
• Traverse Right, PreOrder(right)
• Visit Root

In post-order, we visit root last
- left => right => root

Question 4

What are the advantages depth first traversal over breadth first?

Answer 4

• Depth first on a binary tree generally requires less memory than breadth first
• Depth first can be easily implemented with recursion

Question 5

What are the advantages/disadvantages of breadth first traversal over depth-first?

Answer 5

Breadth first traversal finds the shortest path to a node

BFS requires more memory than DFS