Tree Traversal: Complete Guide

What Is Tree Traversal?

Tree traversal is the process of visiting every node in a tree according to a defined order. Unlike a linear data structure such as an array, a tree has multiple branches, so there are several meaningful ways to visit its nodes.

Tree traversal is used for searching, displaying hierarchical data, evaluating expressions, processing file systems, generating sorted values from binary search trees, and solving many tree-based algorithm problems.

The four commonly studied binary-tree traversal methods are:

• Inorder traversal
• Preorder traversal
• Postorder traversal
• Level-order traversal

Example Tree

We will use the following tree to understand the different traversal orders:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

Every traversal visits all seven nodes, but the order in which they are visited changes.

Depth-First and Breadth-First Traversal

Tree traversal approaches can be broadly divided into depth-first traversal and breadth-first traversal.

Inorder Traversal

Inorder traversal visits the left subtree first, then the current node, and finally the right subtree.

Left → Root → Right

For the example tree, the traversal works as follows:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

Inorder:
20 → 30 → 40 → 50 → 60 → 70 → 80

In a Binary Search Tree, inorder traversal produces values in sorted order. This makes inorder traversal particularly useful when processing ordered tree data.

Preorder Traversal

Preorder traversal visits the current node before visiting its left and right subtrees.

Root → Left → Right

Applying preorder traversal to the example tree gives:

50 → 30 → 20 → 40 → 70 → 60 → 80

Preorder traversal is useful when the parent node needs to be processed before its descendants, such as when representing or copying a tree structure.

Postorder Traversal

Postorder traversal visits both child subtrees before processing the current node.

Left → Right → Root

For the example tree, postorder traversal produces:

20 → 40 → 30 → 60 → 80 → 70 → 50

Postorder traversal is useful when child nodes need to be processed before their parent, such as deleting a tree or evaluating expression trees.

Level-Order Traversal

Level-order traversal visits nodes level by level from top to bottom. Nodes at the same depth are processed before moving to the next level.

Level 0: 50
Level 1: 30, 70
Level 2: 20, 40, 60, 80

Result:
50 → 30 → 70 → 20 → 40 → 60 → 80

Level-order traversal is generally implemented using a queue and is a breadth-first traversal technique.

Recursive Depth-First Traversal

Inorder, preorder, and postorder traversal are naturally expressed using recursion. The only difference between them is when the current node is processed relative to its children.

Inorder

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

Preorder

function preorder(root, result = []) {
  if (root === null) {
    return result;
  }

  result.push(root.value);
  preorder(root.left, result);
  preorder(root.right, result);

  return result;
}

Postorder

function postorder(root, result = []) {
  if (root === null) {
    return result;
  }

  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.value);

  return result;
}

Why the Order Changes the Result

The same tree can produce different sequences because each traversal chooses a different point at which the current node is processed.

Iterative Inorder Traversal

Inorder traversal can also be implemented iteratively using a stack. The stack keeps track of nodes whose right subtrees still need to be processed.

function inorderIterative(root) {
  const stack = [];
  const result = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    result.push(current.value);

    current = current.right;
  }

  return result;
}

The algorithm keeps moving left until it reaches the end of a branch, then processes the most recently stored node before exploring its right subtree.

Iterative Preorder Traversal

Preorder traversal can use a stack containing the nodes that still need to be visited. Because the current node must be processed before its children, it is added to the result as soon as it is removed from the stack.

function preorderIterative(root) {
  if (root === null) {
    return [];
  }

  const stack = [root];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.value);

    if (node.right !== null) {
      stack.push(node.right);
    }

    if (node.left !== null) {
      stack.push(node.left);
    }
  }

  return result;
}

The right child is pushed before the left child because a stack is last-in, first-out. This ensures that the left child is processed first.

Iterative Postorder Traversal

Postorder traversal is more involved iteratively because a node must be processed only after both of its children have been handled.

One straightforward approach uses two stacks:

function postorderIterative(root) {
  if (root === null) {
    return [];
  }

  const stack1 = [root];
  const stack2 = [];
  const result = [];

  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);

    if (node.left !== null) {
      stack1.push(node.left);
    }

    if (node.right !== null) {
      stack1.push(node.right);
    }
  }

  while (stack2.length > 0) {
    result.push(stack2.pop().value);
  }

  return result;
}

Level-Order Traversal Using a Queue

Level-order traversal uses a queue because nodes must be processed in the same order in which they are discovered.

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];
    result.push(node.value);

    if (node.left !== null) {
      queue.push(node.left);
    }

    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}

The index-based queue avoids repeatedly removing the first element of a JavaScript array, which can be less efficient than moving a pointer through the queue.

Traversal Complexity

Every standard traversal visits each node at least once. Therefore, the time complexity of inorder, preorder, postorder, and level-order traversal is O(n), where n is the number of nodes.

Here, h represents the height of the tree and w represents the maximum number of nodes stored at one level. For a skewed tree, h can approach n.

Tree Traversal in Binary Search Trees

Traversal has an especially useful relationship with Binary Search Trees. Inorder traversal of a valid BST produces the stored values in ascending order.

BST:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Inorder:
20, 30, 40, 50, 60, 70, 80

This property makes inorder traversal useful for producing sorted output from a BST.

Choosing the Right Traversal

The appropriate traversal depends on what needs to happen during node processing.

• Inorder: useful when values need to be processed in sorted order from a BST.
• Preorder: useful when a parent should be processed before its descendants.
• Postorder: useful when children must be processed before their parent.
• Level-order: useful when processing a tree one level at a time.

Common Tree Traversal Mistakes

• Confusing inorder with preorder or postorder.
• Forgetting the base case when using recursion.
• Processing the current node at the wrong point in the recursive function.
• Using a stack incorrectly during iterative traversal.
• Processing children in the wrong order during preorder traversal.
• Using a stack instead of a queue for standard level-order traversal.
• Assuming inorder traversal is sorted for every binary tree rather than specifically for a valid BST.

Tree Traversal in Real Applications

Tree traversal is used in many areas of software development because hierarchical data appears in databases, file systems, compilers, document structures, and application interfaces.

• File and directory processing
• DOM and document tree processing
• Expression tree evaluation
• Binary search tree operations
• Hierarchical menu processing
• Tree-based algorithm problems
• Searching and filtering hierarchical data

Key Takeaways

• Tree traversal means visiting every node according to a defined order.
• Inorder follows Left → Root → Right.
• Preorder follows Root → Left → Right.
• Postorder follows Left → Right → Root.
• Level-order visits nodes one level at a time.
• Inorder traversal of a valid BST produces sorted values.
• Depth-first traversals can be implemented recursively or with a stack.
• Level-order traversal is commonly implemented using a queue.
• Standard tree traversal takes O(n) time because every node is visited.