EdTech

3 · Trees · Data Structures

Tree Traversal

·

Why Tree Traversal Needs an Order

A binary tree is non-linear: a node can lead to a left subtree and a right subtree. To process every node exactly once, a traversal must specify the order in which nodes are visited.

This page considers depth-first traversal of binary trees. The three main orders differ only in when the current node is visited relative to its left and right subtrees.

The Recursive Traversal Pattern

Each child of a node is the root of another binary tree. This makes recursion a natural fit.

The base case is an empty tree: perform no action. For a non-empty node, recursively process its subtrees and visit the node at the position required by the chosen order.

traverse(node):
    if node is empty:
        return

    // place visit(node) before, between, or after
    // traversal calls for the two child subtrees

The empty-tree check is essential because a leaf has empty left and right subtrees.

Inorder, Preorder, and Postorder

Let visit(node) mean any required processing, such as displaying the node value.

Traversal Order Recursive pattern
Inorder left subtree, node, right subtree inorder(left); visit(node); inorder(right)
Preorder node, left subtree, right subtree visit(node); preorder(left); preorder(right)
Postorder left subtree, right subtree, node postorder(left); postorder(right); visit(node)

For the binary tree below, the traversal order is determined by the location of visit(node).

        A
       / \
      B   C
     / \
    D   E

For example, preorder visits A first, then completely processes the left subtree rooted at B, and finally processes the right subtree rooted at C.

Cost of Inorder Traversal

For a binary search tree with n nodes, inorder traversal visits each node once:

[ T(n) = O(n) ]

This time complexity is O(n) whether the binary search tree is balanced or unbalanced. The tree shape can change the recursion depth, but every node is still visited once.

Practice: Trace and Write Traversals

  1. For the tree below, write its inorder, preorder, and postorder traversals.

        8
       / \
      3   10
         /  \
        9   14
  2. Complete the recursive preorder procedure by placing the three operations in the correct order: visit(node), preorder(node.left), and preorder(node.right). Include the empty-tree base case.

  3. A binary search tree has n nodes and is highly unbalanced. What is the time complexity of its inorder traversal? Explain using the number of node visits.

Common Mistakes

Key Takeaways

Sources

  1. Binary Tree Traversal — NPTEL. Accessed 24 September 2026.
  2. Programming, Data Structures and Algorithms using C — Week 6 Assignment — NPTEL. Accessed 24 September 2026.
  3. Design and Analysis of Algorithms — Assessments — NPTEL. Accessed 24 September 2026.

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/106103069/Module_9/traversal.htm — archive.nptel.ac.in (Generated candidate citation)
  2. Programming, Data Structures and Algorithms using C — Week 6 Assignment — NPTEL (Generated candidate citation)
  3. Design and Analysis of Algorithms — Assessments — NPTEL (Generated candidate citation)

Related topics