Tree Traversal

Introduction

Tree traversal is the process of visiting all vertices in a tree in a systematic order. Different traversal methods serve different purposes.

Why Traverse Trees?

Applications:

• Searching for a value
• Printing tree contents
• Evaluating expressions
• Copying a tree
• Converting between representations

Types of Traversal

Main categories:

1. Depth-First Search (DFS) - Go deep before wide
2. Breadth-First Search (BFS) - Go wide before deep

Depth-First Traversal (DFS)

Overview

Explore as far as possible along each branch before backtracking.

Three DFS orderings:

1. Preorder (Root → Left → Right)
2. Inorder (Left → Root → Right)
3. Postorder (Left → Right → Root)

Example Tree for DFS

      1
     / \
    2   3
   / \
  4   5

1. Preorder Traversal

Order: Root → Left subtree → Right subtree

Process:

1. Visit root
2. Traverse left subtree in preorder
3. Traverse right subtree in preorder

Example:

      1  ← visit first
     / \
    2   3
   / \
  4   5

Steps:

1. Visit 1
2. Go left: Visit 2
3. Go left from 2: Visit 4
4. Backtrack to 2, go right: Visit 5
5. Backtrack to 1, go right: Visit 3

Result: 1, 2, 4, 5, 3

Preorder Algorithm (Recursive)

Preorder(node):
    if node is NULL:
        return

    Visit(node)              // Process root
    Preorder(node.left)      // Left subtree
    Preorder(node.right)     // Right subtree

Time Complexity: O(n) - visits each node once Space Complexity: O(h) - recursion stack, h = height

2. Inorder Traversal

Order: Left subtree → Root → Right subtree

Process:

1. Traverse left subtree in inorder
2. Visit root
3. Traverse right subtree in inorder

Example:

      1
     / \
    2   3
   / \
  4   5

Steps:

1. Go left to 2
2. Go left to 4
3. Visit 4 (no left child)
4. Backtrack, visit 2
5. Go right, visit 5
6. Backtrack, visit 1
7. Go right, visit 3

Result: 4, 2, 5, 1, 3

Inorder Algorithm (Recursive)

Inorder(node):
    if node is NULL:
        return

    Inorder(node.left)       // Left subtree
    Visit(node)              // Process root
    Inorder(node.right)      // Right subtree

Special Property: For Binary Search Trees, inorder gives sorted order!

3. Postorder Traversal

Order: Left subtree → Right subtree → Root

Process:

1. Traverse left subtree in postorder
2. Traverse right subtree in postorder
3. Visit root

Example:

      1
     / \
    2   3
   / \
  4   5

Steps:

1. Go left to 2, then left to 4
2. Visit 4 (no children)
3. Backtrack to 2, go right to 5
4. Visit 5
5. Visit 2 (both children done)
6. Backtrack to 1, go right to 3
7. Visit 3
8. Visit 1 (all children done)

Result: 4, 5, 2, 3, 1

Postorder Algorithm (Recursive)

Postorder(node):
    if node is NULL:
        return

    Postorder(node.left)     // Left subtree
    Postorder(node.right)    // Right subtree
    Visit(node)              // Process root

Use Case: Deleting tree nodes (children before parent)

Breadth-First Traversal (BFS)

Level-Order Traversal

Order: Visit all nodes at level 0, then level 1, then level 2, etc.

Example:

Level 0:      1
             / \
Level 1:    2   3
           / \
Level 2:  4   5

Result: 1, 2, 3, 4, 5

Level-Order Algorithm

Uses a queue:

LevelOrder(root):
    if root is NULL:
        return

    queue = empty queue
    queue.enqueue(root)

    while queue is not empty:
        node = queue.dequeue()
        Visit(node)

        if node.left exists:
            queue.enqueue(node.left)
        if node.right exists:
            queue.enqueue(node.right)

Time Complexity: O(n) Space Complexity: O(w) where w = maximum width

Example: Level-Order Step-by-Step

Tree:

      1
     / \
    2   3
   / \   \
  4   5   6

Steps:

1. Queue: [1], Visit 1
2. Queue: [2, 3], Visit 2, enqueue children
3. Queue: [3, 4, 5], Visit 3, enqueue child
4. Queue: [4, 5, 6], Visit 4
5. Queue: [5, 6], Visit 5
6. Queue: [6], Visit 6
7. Queue: [], Done

Result: 1, 2, 3, 4, 5, 6

Comparison of Traversals

Visual Example

Tree:

      A
     / \
    B   C
   / \   \
  D   E   F

Preorder: A, B, D, E, C, F Inorder: D, B, E, A, C, F Postorder: D, E, B, F, C, A Level-order: A, B, C, D, E, F

Applications of Each Traversal

Preorder

Use cases:

1. Copy a tree (create root first)
2. Prefix expression evaluation
3. Serialize tree to file
4. Pre-processing before processing children

Example: Copying a tree

CopyTree(node):
    if node is NULL:
        return NULL

    newNode = CreateNode(node.data)  // Create root first
    newNode.left = CopyTree(node.left)
    newNode.right = CopyTree(node.right)
    return newNode

Inorder

Use cases:

1. Binary Search Tree → sorted order
2. Infix expression from expression tree
3. Validate BST property

Example: BST to sorted array

InorderBST(node, array):
    if node is NULL:
        return

    InorderBST(node.left, array)
    array.append(node.data)      // Add in sorted order
    InorderBST(node.right, array)

Postorder

Use cases:

1. Delete tree (delete children before parent)
2. Postfix expression evaluation
3. Calculate folder sizes (files before directories)
4. Post-processing after children

Example: Delete tree

DeleteTree(node):
    if node is NULL:
        return

    DeleteTree(node.left)    // Delete left child
    DeleteTree(node.right)   // Delete right child
    Free(node)               // Delete node itself

Level-Order

Use cases:

1. Print tree level by level
2. Find width of tree
3. Serialize tree with NULL markers
4. Shortest path in unweighted tree

Expression Trees

Building from Traversals

Example: Expression tree for (a + b) * c

      *
     / \
    +   c
   / \
  a   b

Preorder (Prefix): _ + a b c Inorder (Infix): a + b _ c (needs parentheses!) Postorder (Postfix): a b + c *

Evaluating Expression Tree

Postorder evaluation:

Evaluate(node):
    if node is leaf:
        return node.value

    left = Evaluate(node.left)
    right = Evaluate(node.right)
    return Apply(node.operator, left, right)

Example:

      *
     / \
    +   3
   / \
  1   2

1. Evaluate left: 1 + 2 = 3
2. Evaluate right: 3
3. Result: 3 * 3 = 9

Constructing Tree from Traversals

Inorder + Preorder → Unique Tree

Given:

• Inorder: D, B, E, A, C, F
• Preorder: A, B, D, E, C, F

Steps:

1. First element of preorder is root: A
2. Find A in inorder: [D, B, E] | A | [C, F]
3. Left subtree has inorder: D, B, E
4. Right subtree has inorder: C, F
5. Recursively build subtrees

Result:

      A
     / \
    B   C
   / \   \
  D   E   F

Inorder + Postorder → Unique Tree

Given:

• Inorder: D, B, E, A, C, F
• Postorder: D, E, B, F, C, A

Steps:

1. Last element of postorder is root: A
2. Find A in inorder: [D, B, E] | A | [C, F]
3. Recursively build subtrees

Result: Same tree as above

Cannot Construct from Preorder + Postorder

Ambiguous! Need inorder to determine left/right.

Iterative Traversals

Iterative Preorder (Using Stack)

IterativePreorder(root):
    if root is NULL:
        return

    stack = empty stack
    stack.push(root)

    while stack is not empty:
        node = stack.pop()
        Visit(node)

        if node.right exists:
            stack.push(node.right)  // Push right first
        if node.left exists:
            stack.push(node.left)   // So left is processed first

Iterative Inorder (Using Stack)

IterativeInorder(root):
    stack = empty stack
    current = root

    while current is not NULL or stack is not empty:
        while current is not NULL:
            stack.push(current)
            current = current.left

        current = stack.pop()
        Visit(current)
        current = current.right

Morris Traversal (Advanced)

Advantage: O(1) space (no stack/recursion)

Idea: Use “threaded” pointers temporarily

Use case: When memory is extremely limited

Key Points for Exams

1. Preorder: Root, Left, Right
2. Inorder: Left, Root, Right
3. Postorder: Left, Right, Root
4. Level-order: Level by level (BFS)
5. Inorder of BST: sorted order
6. Postorder: used for deletion
7. Preorder: used for copying
8. All DFS: O(n) time, O(h) space
9. Level-order: uses queue, O(n) time
10. Inorder + Preorder: can reconstruct unique tree

Practice Problems

1. Given tree, find preorder:

      5
     / \
    3   7
   / \
  1   4

2. What is inorder traversal of above tree?

3. Write postorder traversal of:

      A
     / \
    B   C
   /
  D

4. Given Inorder: [4,2,5,1,3] and Preorder: [1,2,4,5,3], draw the tree.

5. Why is inorder special for Binary Search Trees?

6. Which traversal is best for deleting a tree? Why?

7. Implement level-order using queue (pseudocode).

8. Can you construct unique tree from Preorder + Postorder alone? Explain.

9. For expression tree of “(a+b)*c”, write all four traversals.

10. What is the space complexity of recursive preorder traversal?