14 Tree Traversal

Preorder

		A
     /   \
    B     C
   / \     \
  D   E     F

We visit nodes in the order: Root → Left → Right

1. Visit A
2. Move to left subtree (B)
   • Visit B
   • Move to left subtree (D) → Visit D
   • Move to right subtree (E) → Visit E
3. Back to A, move to right subtree (C)
   • Visit C
   • Move to right subtree (F) → Visit F

Postorder Traversal Steps:

We visit nodes in the order: Left → Right → Root

1. Start at A
2. Move to left subtree (B)
   • Move to left subtree (D) → Visit D
   • Move to right subtree (E) → Visit E
   • Done with B’s children → Visit B
3. Move to right subtree (C)
   • C has no left child
   • Move to right subtree (F) → Visit F
   • Done with C’s children → Visit C
4. Done with A’s children → Visit A

Level-order Traversal Steps:

Not possible recursively
We visit nodes level by level, from top to bottom, left to right within each level.

1. Level 0: Visit A
2. Level 1: Visit B, C
3. Level 2: Visit D, E, F

On BST

		5
      / \
     3   8
    / \   \
   1   4   9

Preorder: $[5,3,1,4,8,9]$
Postorder: $[1,4,3,9,8]$