Binary Tree Traversal: Navigating Binary Trees Effectively • Chillymosh's Blog

In our previous post, Binary Trees 101, we introduced the basics of binary trees, covering their structures, properties, and practical representations. Now that you’ve got a solid grasp of binary tree fundamentals, let’s explore one of the most essential concepts when working with these data structures: tree traversals.

Traversals allow us to systematically visit each node in a binary tree, serving as the foundation for many critical operations like searching, inserting, and deleting data.

Key Topics#

Recursive vs Iterative Approaches: The two main strategies for traversing trees.
Traversal Techniques: Pre-order, in-order, post-order, and level-order traversals, each with distinct characteristics and use-cases.
Real-world Applications: Understanding when and why to use each traversal type, such as in-order for Binary Search Trees (BSTs).

DFS vs BFS Traversals#

There are two fundamental strategies for traversing trees:

Depth-First Search (DFS):
Explores as deep as possible down each branch before backtracking.
Includes: Pre-order, In-order, and Post-order traversals.
Breadth-First Search (BFS):
Explores all nodes at each level before moving to the next.
Includes: Level-order traversal.

Types of Tree Traversals#

Before diving into code, let’s cover the core strategies for traversing a binary tree:

Recursive: Leverages the language’s call stack, naturally mirroring the tree’s structure. Most traversal algorithms are elegant and concise in recursive form.
Iterative: Uses explicit data structures like stacks (for DFS) or queues (for BFS) to manage traversal state, which can avoid recursion limits and sometimes improve performance.

Traversal Orders & Use-Cases#

Traversal	Order	Real-World Uses	DFS/BFS
Pre-order	Root, Left, Right	Cloning trees, prefix expression trees	DFS
In-order	Left, Root, Right	Retrieving sorted data from BSTs	DFS
Post-order	Left, Right, Root	Deleting/freeing trees, postfix evaluation	DFS
Level-order	Level by level (L→R)	Printing, serialisation, BFS/shortest path	BFS

Traversal Examples#

Pre-order Traversal (Root, Left, Right)#

Pre-order traversal visits the root node first, then explores the left subtree, followed by the right subtree. It’s called pre-order because each node is processed before its left and right subtrees are visited.

For the tree above, pre-order traversal visits nodes in the order shown: R, A, C, D, B, E, F, G.
This order stays the same whether you use recursion or an explicit stack (iterative approach).

Recursive#

The recursive version uses the programming language’s call stack to keep track of where it is in the tree.

Visit the Node: At each function call, process the current node (e.g. print its value or add it to a result list).
Traverse Left: Recursively call the function on the node’s left child. This continues down the leftmost path first.
Traverse Right: After finishing the left subtree, recursively call the function on the node’s right child.
Base Case: If the function reaches a node that is None (or null), it returns immediately—meaning there’s nothing left to visit at that branch.

def preorder(node: Node):
  if not node:
      return
  print(node.value)       # Visit the node
  preorder(node.left)     # Traverse left subtree
  preorder(node.right)    # Traverse right subtree

function preorder(node) {
  if (!node) return;
  console.log(node.value);   // Visit the node
  preorder(node.left);       // Traverse left subtree
  preorder(node.right);      // Traverse right subtree
}

func preorder(node *Node) {
    if node == nil {
        return
    }
    fmt.Println(node.Value) // Visit the node
    preorder(node.Left)     // Traverse left subtree
    preorder(node.Right)    // Traverse right subtree
}

public void preorder(Node node) {
    if (node == null) return;
    System.out.println(node.value);   // Visit the node
    preorder(node.left);             // Traverse left subtree
    preorder(node.right);            // Traverse right subtree
    }

java

public void Preorder(Node node) {
    if (node == null) return;
    Console.WriteLine(node.Value);  // Visit the node
    Preorder(node.Left);            // Traverse left subtree
    Preorder(node.Right);           // Traverse right subtree
}

void preorder(Node* node) {
    if (!node) return;
    cout << node->value << endl;   // Visit the node
    preorder(node->left);          // Traverse left subtree
    preorder(node->right);         // Traverse right subtree
}

void preorder(Node *node) {
    if (node == NULL) return;
    printf("%d\n", node->val);  // Visit the node
    preorder(node->left);       // Traverse left subtree
    preorder(node->right);      // Traverse right subtree
}

fn preorder(root: &Option<Box<Node>>) {
    match root {
        None => return,
        Some(node) => {
            println!("{}", node.val);
            preorder(&node.left);
            preorder(&node.right);
        }
    }
}

Iterative#

Instead of using recursion, the iterative version explicitly manages the nodes to visit using a stack.

Initialization: Start by pushing the root node onto the stack.
Processing: While the stack isn’t empty, pop the top node, visit it (add its value to the result list), and then push its right and left children (if any) onto the stack.
Order: By pushing the right child before the left child, we ensure the left child is processed first (since stacks are LIFO—last in, first out).
Repeat: Continue this process until there are no more nodes left in the stack.

def preorder(root: Node):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        # Right child is pushed first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

function preorder(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);
    // Right child is pushed first so left child is processed first
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

func preorder(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    stack := []*TreeNode{root}
    result := []int{}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return result
}

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;

public class Solution {
    public List<Integer> preorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left  != null) stack.push(node.left);
        }
        return result;
    }
}

java

In-order Traversal (Left, Root, Right)#

In-order traversal explores the left subtree first, then processes the root node, and finally visits the right subtree. This approach is especially valuable for Binary Search Trees, as it retrieves values in ascending order.

It’s called in-order because each node is visited between traversing its left and right subtrees, after finishing the left, but before starting the right.

For the tree above, pre-order traversal visits nodes in the order shown: C, A, D, R, E, B, G, F.
This order stays the same whether you use recursion or an explicit stack (iterative approach).

Recursive#

Traverse Left: Recursively call the function on the node’s left child, moving as far left as possible in the tree.
Visit the Node: Once there are no more left children, process the current node (e.g. print its value or add it to a result list).
Traverse Right: After visiting the node, recursively call the function on the right child to process the right subtree.
Base Case: If the function reaches a None (or null) node, it returns immediately—meaning there’s nothing left to visit in that branch.

def inorder(node: Node):
  if not node:
      return     
  inorder(node.left)     # Traverse left subtree
  print(node.value)      # Visit the node
  inorder(node.right)    # Traverse right subtree

function inorder(node) {
  if (!node) return;
  inorder(node.left);       // Traverse left subtree
  console.log(node.value);  // Visit the node
  inorder(node.right);      // Traverse right subtree
}

func inorder(node *Node) {
    if node == nil {
        return
    }
    inorder(node.Left)     // Traverse left subtree
    fmt.Println(node.Value) // Visit the node
    inorder(node.Right)    // Traverse right subtree
}

public void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);             // Traverse left subtree
    System.out.println(node.value);   // Visit the node
    inorder(node.right);            // Traverse right subtree
    }

java

public void Inorder(Node node) {
    if (node == null) return;
    Inorder(node.Left);            // Traverse left subtree
    Console.WriteLine(node.Value);  // Visit the node
    Inorder(node.Right);           // Traverse right subtree
}

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);          // Traverse left subtree
    cout << node->value << endl;   // Visit the node
    inorder(node->right);         // Traverse right subtree
}

void inorder(Node *node) {
    if (node == NULL) return;
    inorder(node->left);       // Traverse left subtree
    printf("%d\n", node->val);  // Visit the node
    inorder(node->right);      // Traverse right subtree
}

fn inorder(root: &Option<Box<Node>>) {
    match root {
        None => return,
        Some(node) => {
            inorder(&node.left);
            println!("{}", node.val);
            inorder(&node.right);
        }
    }
}

Iterative#

Initialization: Start with an empty stack and set the current node to the root.
Go Left: Move as far left as possible, pushing each node onto the stack as you go.
Visit the Node: Once you reach a node with no left child, pop a node from the stack and process it (print/add its value).
Go Right: After visiting the node, move to its right child and repeat the process.
Repeat: Continue this loop (go left, visit, go right) until both the stack is empty and there are no more nodes to process.

Python
Javascript

def inorder(root: Node):
  stack = []
  result = []
  curr = root
  while stack or curr:
      while curr:
          stack.append(curr)
          curr = curr.left
      curr = stack.pop()
      result.append(curr.value)
      curr = curr.right
  return result

function inorder(root) {
  const stack = [];
  const result = [];
  let curr = root;
  while (stack.length > 0 || curr) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.value);
    curr = curr.right;
  }
  return result;
}

Post-order Traversal (Left, Right, Root)#

Post-order traversal explores the left subtree first, then the right subtree, and processes the current node last. This approach is particularly useful for tasks like deleting a tree, since you want to delete children before the parent, or evaluating postfix expressions.

It’s called post-order because each node is processed after both its subtrees have been visited.

For the tree above, post-order traversal visits nodes in the order shown: C, D, A, E, G, F, B, R.
This order stays the same whether you use recursion or an explicit stack (iterative approach).

Recursive#

Traverse Left: Recursively call the function on the node’s left child.
Traverse Right: Recursively call the function on the node’s right child.
Visit the Node: Process the current node (e.g. print its value or add it to a result list).
Base Case: If the function reaches a node that is None (or null), it returns immediately.

def postorder(node: Node):
  if not node:
      return
  postorder(node.left)     # Traverse left subtree
  postorder(node.right)    # Traverse right subtree
  print(node.value)        # Visit the node

function postorder(node) {
  if (!node) return;
  postorder(node.left);       // Traverse left subtree
  postorder(node.right);      // Traverse right subtree
  console.log(node.value);    // Visit the node
}

func postorder(node *Node) {
    if node == nil {
        return
    }
    postorder(node.Left)     // Traverse left subtree
    postorder(node.Right)    // Traverse right subtree
    fmt.Println(node.Value)  // Visit the node
}

public void postorder(Node node) {
    if (node == null) return;
    postorder(node.left);             // Traverse left subtree
    postorder(node.right);            // Traverse right subtree
    System.out.println(node.value);   // Visit the node
    }

java

public void Postorder(Node node) {
    if (node == null) return;
    Postorder(node.Left);            // Traverse left subtree
    Postorder(node.Right);           // Traverse right subtree
    Console.WriteLine(node.Value);   // Visit the node
}

void postorder(Node* node) {
    if (!node) return;
    postorder(node->left);          // Traverse left subtree
    postorder(node->right);         // Traverse right subtree
    cout << node->value << endl;    // Visit the node
}

void postorder(Node *node) {
    if (node == NULL) return;
    postorder(node->left);       // Traverse left subtree
    postorder(node->right);      // Traverse right subtree
    printf("%d\n", node->val);  // Visit the node
}

fn postorder(root: &Option<Box<Node>>) {
    match root {
        None => return,
        Some(node) => {
            postorder(&node.left);
            postorder(&node.right);
            println!("{}", node.val);
        }
    }
}

Iterative#

Instead of recursion, the iterative version explicitly manages nodes to visit using a stack. Post-order is trickier to implement iteratively than pre-order or in-order.

Initialization: Start by pushing the root node onto the stack.
Processing: Pop nodes from the stack, and push them onto a visited stack, or prepend their value to the result list. Push left child first, then right child, so right is processed before left.
Repeat: Continue until the stack is empty.
Result: The visited stack or reversed result list gives the post-order traversal.

Python
Javascript

def postorder(root: Node):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]  # Reverse the result list

function postorder(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.value);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return result.reverse();
}

Advanced: True Iterative Post-order#

While the reverse pre-order trick is great for collecting values, sometimes you need to process a node only after both children are finished (e.g. to free nodes or modify the tree). Here are two classic techniques for this:

One Stack With Visited State: Use a single stack but track the last visited node. Only process a node after both its left and right children are done. This approach closely matches recursion, but is more complex to implement.
Two Stack Method: Use one stack for traversal and a second stack, or list, to collect the nodes in post-order. This also results in O(n) time and space.

These approaches are more advanced, and not usually needed for simple traversals, but they’re useful to know about.

Click to see a one-stack iterative post-order example

Python
Javascript

def postorder(root: Node):
    stack = []
    result = []
    last_visited = None
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                curr = peek.right
            else:
                result.append(peek.value)
                last_visited = stack.pop()
    return result

function postorder(root) {
  const stack = [];
  const result = [];
  let lastVisited = null;
  let curr = root;
  while (stack.length > 0 || curr) {
    if (curr) {
      stack.push(curr);
      curr = curr.left;
    } else {
      const peek = stack[stack.length - 1];
      if (peek.right && lastVisited !== peek.right) {
        curr = peek.right;
      } else {
        result.push(peek.value);
        lastVisited = stack.pop();
      }
    }
  }
  return result;
}

Click to see a two-stack iterative post-order example

Python
Javascript

def postorder(root: Node):
    if not root:
        return []
    stack1 = [root]
    stack2 = []
    result = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        result.append(stack2.pop().value)
    return result

function postorder(root) {
  if (!root) return [];
  const stack1 = [root];
  const stack2 = [];
  const result = [];
  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);
    if (node.left) stack1.push(node.left);
    if (node.right) stack1.push(node.right);
  }
  while (stack2.length > 0) {
    result.push(stack2.pop().value);
  }
  return result;
}

Level-order Traversal (BFS)#

Level-order traversal visits all nodes at each depth of the tree, starting from the root and working level by level from left to right. This method is also known as breadth-first traversal, as it explores all nodes on one level before moving to the next.

Level-order traversal is essential for:
Printing a tree level by level, like a hierarchy or org chart.
Finding the shortest path in an unweighted tree
Serialising and deserialising trees for storage or transmission
Solving problems that require processing nodes in order of their depth

For the tree above, level-order traversal visits nodes by row, starting from the root: R, A, B, C, D, E, F, G. This order ensures all nodes at depth n are visited before any node at depth n+1.

Level-order traversal is most naturally implemented using a queue (FIFO), rather than a stack, or recursively.

Iterative#

Initialization: Start by enqueueing the root node.
Processing: While the queue isn’t empty:

Dequeue the front node and process it (e.g. print/add its value).
Enqueue its left child, if any, then its right child, if any.

Repeat: Continue until the queue is empty.

from collections import deque

def levelorder(root: Node):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

function levelorder(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

func levelOrder(root *TreeNode) []int {
if root == nil {
    return nil
}
queue := []*TreeNode{root}
result := []int{}
for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    result = append(result, node.Val)
    if node.Left != nil {
        queue = append(queue, node.Left)
    }
    if node.Right != nil {
        queue = append(queue, node.Right)
    }
}
return result
}

Recursive#

Level-order traversal is rarely implemented recursively because recursion alone doesn’t naturally handle breadth-first order. However, it can be done using a helper function that visits nodes by their level:

Python
Javascript

def levelorder(root):
    def helper(node, level, levels):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.value)
        helper(node.left, level + 1, levels)
        helper(node.right, level + 1, levels)
    levels = []
    helper(root, 0, levels)
    return [val for sublist in levels for val in sublist]

function levelorder(root) {
  const levels = [];
  function helper(node, level) {
    if (!node) return;
    if (levels.length === level) levels.push([]);
    levels[level].push(node.value);
    helper(node.left, level + 1);
    helper(node.right, level + 1);
  }
  helper(root, 0);
  return levels.flat();
}

Recap#

Hopefully, you now know the four essential ways to traverse a binary tree: pre-order, in-order, post-order, and level-order. Each with their own strengths, typical applications, and recursive or iterative solutions. These patterns form the backbone of almost every binary tree algorithm, from basic searches to complex transformations. The examples will be updated over time other languages.

Up Next: Binary Search Trees (BSTs)#

In our next post, we’ll explore one of the most powerful uses of binary trees: the Binary Search Tree (BST).

We’ll cover:

How BSTs organize data for fast search, insert, and delete operations
Step-by-step BST algorithms (with code and visuals)
How to analyse best-case and worst-case performance
Common pitfalls, balancing needs, and when to use BSTs in practice

Stay tuned for Binary Search Trees: Fast Search, Insert, & Delete coming next!