sreejithmvarma.in

PCCST303 · Module 3: Trees and Graphs

Tree Traversals

Traversal means visiting every node in a tree exactly once, in a systematic order. Unlike a linked list, where "visit every element" has only one sensible order, a tree branches, so there's more than one reasonable way to walk it.

The tree used throughout this page:

DEBFGCA

KTU PYQ

KTU PYQ, November 2025, Q13(b), 3 marks: "Write algorithm for different tree traversals."

To answer this, give the three depth-first algorithms: preorder, inorder, and postorder. The purple-bordered sections below answer this.

Preorder: root, left, right

Definition

Preorder visits the root first, then recursively traverses the left subtree, then the right subtree.

PREORDER(ROOT)
 
1. If ROOT == NULL:
       Return
2. PRINT ROOT->data
3. PREORDER(ROOT->left)
4. PREORDER(ROOT->right)

Visiting the root before either subtree means the root is always printed first, then everything under the left child, then everything under the right child. Press Play to watch the visit order build up: A B D E C F G, A first, then B's whole side (B D E), then C's whole side (C F G).

DEBFGCA
Output:???????

Inorder: left, root, right

Definition

Inorder traverses the left subtree first, then visits the root, then traverses the right subtree.

INORDER(ROOT)
 
1. If ROOT == NULL:
       Return
2. INORDER(ROOT->left)
3. PRINT ROOT->data
4. INORDER(ROOT->right)

The root is printed only after its entire left subtree is done, and before its right subtree starts. Press Play to watch: D B E A F C G, everything under B (D B E), then A, then everything under C (F C G).

DEBFGCA
Output:???????

Key Idea

If you run inorder traversal on a binary search tree, the values come out sorted. This isn't a coincidence: a BST always keeps smaller values to the left and larger values to the right, and inorder visits left, then root, then right, so it naturally reads the values off in increasing order.

Postorder: left, right, root

Definition

Postorder traverses the left subtree, then the right subtree, and visits the root last.

POSTORDER(ROOT)
 
1. If ROOT == NULL:
       Return
2. POSTORDER(ROOT->left)
3. POSTORDER(ROOT->right)
4. PRINT ROOT->data

The root is printed only after both of its subtrees are completely done. Press Play to watch: D E B F G C A, everything under B (D E B), then everything under C (F G C), then A last.

DEBFGCA
Output:???????

One tree, three orders

The only difference between the three is when the root is visited relative to its subtrees: preorder visits it first, inorder visits it between the two subtrees, postorder visits it last. Memory trick: pre = root comes first, in = root comes in-between, post = root comes last. 
Preorder:  A B D E C F G
Inorder:   D B E A F C G
Postorder: D E B F G C A

Level order traversal

Preorder, inorder, and postorder are all depth-first: they follow one branch as deep as it goes before backtracking. Level order is different, it's breadth-first, visiting all nodes at depth 0, then all nodes at depth 1, and so on.

A queue is naturally suited to this, the same FIFO structure used for BFS on graphs:

LEVEL_ORDER(ROOT)
 
1. If ROOT == NULL:
       Return
2. Create empty queue Q.
3. ENQUEUE(Q, ROOT)
4. While Q is not empty:
       NODE = DEQUEUE(Q)
       PRINT NODE->data
       If NODE->left != NULL:
           ENQUEUE(Q, NODE->left)
       If NODE->right != NULL:
           ENQUEUE(Q, NODE->right)

Each node enqueues its children right after being printed, so the queue naturally drains level by level: A enqueues B, C; printing B enqueues D, E; printing C enqueues F, G, giving the queue order B, C, D, E, F, G. Press Play to watch the output build level by level:

DEBFGCA
Output:???????
Output for the tree above:
A B C D E F G

Traversal complexity

Every node is visited exactly once, regardless of which traversal:

Time = O(n)

The three depth-first traversals are naturally recursive, and recursion uses call-stack space proportional to how deep the recursion goes, the tree's height:

Auxiliary space = O(h)
For a balanced tree, h = O(log n), so the extra space is small. For a skewed tree, h = O(n), so a deep recursive traversal can use as much stack space as a full pass over a linked list.

Level-order traversal uses a queue instead of the call stack, and that queue never holds more than one level's worth of nodes at a time. So its space depends on the tree's widest level, not its height.

Quick recall

  • Preorder (root, left, right), inorder (left, root, right), postorder (left, right, root): all depth-first, differing only in when the root is visited.
  • Inorder traversal of a BST gives sorted order.
  • Level order is breadth-first, implemented with a queue, visiting nodes level by level.
  • All traversals are O(n) time; depth-first recursion uses O(h) auxiliary stack space, level-order uses a queue sized by the widest level.