Binary Tree Traversals Explained

Understanding Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Tree traversal means visiting every node in the tree exactly once in a specific order. There are two main categories:Depth-First Search (DFS) and Breadth-First Search (BFS).

// Binary Tree Node Definition
class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null

  constructor(val: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val
    this.left = left ?? null
    this.right = right ?? null
  }
}

// Example tree:
//       1
//      / \
//     2   3
//    / \
//   4   5

Depth-First Search (DFS) Traversals

DFS explores as far as possible along each branch before backtracking. There are three variations based on when you "visit" the current node relative to its children.

1. Preorder Traversal (Root → Left → Right)

Visit the current node first, then recursively traverse the left subtree, then the right subtree. Use case: Creating a copy of the tree, serialization, or getting prefix expressions.

// Recursive Preorder
function preorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = []

  function traverse(node: TreeNode | null) {
    if (!node) return

    result.push(node.val)      // Visit root
    traverse(node.left)        // Traverse left
    traverse(node.right)       // Traverse right
  }

  traverse(root)
  return result
}

// Iterative Preorder (using stack)
function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return []

  const result: number[] = []
  const stack: TreeNode[] = [root]

  while (stack.length > 0) {
    const node = stack.pop()!
    result.push(node.val)

    // Push right first so left is processed first (LIFO)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }

  return result
}

// Example: [1, 2, 4, 5, 3]

2. Inorder Traversal (Left → Root → Right)

Traverse the left subtree first, then visit the current node, then traverse the right subtree. Key insight: For a Binary Search Tree (BST), inorder traversal gives nodes in sorted ascending order. This is extremely useful for BST validation and finding kth smallest element.

// Recursive Inorder
function inorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = []

  function traverse(node: TreeNode | null) {
    if (!node) return

    traverse(node.left)        // Traverse left
    result.push(node.val)      // Visit root
    traverse(node.right)       // Traverse right
  }

  traverse(root)
  return result
}

// Iterative Inorder (trickier - track visited nodes)
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = []
  const stack: TreeNode[] = []
  let current: TreeNode | null = root

  while (current || stack.length > 0) {
    // Go as far left as possible
    while (current) {
      stack.push(current)
      current = current.left
    }

    // Process current node
    current = stack.pop()!
    result.push(current.val)

    // Move to right subtree
    current = current.right
  }

  return result
}

// Example: [4, 2, 5, 1, 3]
// For BST: gives sorted order!

3. Postorder Traversal (Left → Right → Root)

Traverse the left subtree, then the right subtree, and finally visit the current node.Use case: Deleting a tree (must delete children before parent), calculating directory sizes, or getting postfix expressions.

// Recursive Postorder
function postorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = []

  function traverse(node: TreeNode | null) {
    if (!node) return

    traverse(node.left)        // Traverse left
    traverse(node.right)       // Traverse right
    result.push(node.val)      // Visit root
  }

  traverse(root)
  return result
}

// Iterative Postorder (using two stacks)
function postorderIterative(root: TreeNode | null): number[] {
  if (!root) return []

  const result: number[] = []
  const stack1: TreeNode[] = [root]
  const stack2: TreeNode[] = []

  // First pass: similar to preorder but push to stack2
  while (stack1.length > 0) {
    const node = stack1.pop()!
    stack2.push(node)

    // Push left first, then right
    if (node.left) stack1.push(node.left)
    if (node.right) stack1.push(node.right)
  }

  // Second pass: pop from stack2 to get postorder
  while (stack2.length > 0) {
    result.push(stack2.pop()!.val)
  }

  return result
}

// Example: [4, 5, 2, 3, 1]

Breadth-First Search (BFS) - Level Order Traversal

BFS visits nodes level by level, from left to right. It uses a queue instead of a stack. Use case: Finding shortest path in unweighted graphs, level-by-level processing, or finding minimum depth.

// Level Order Traversal (returns 2D array by level)
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []

  const result: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    const currentLevel: number[] = []

    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      currentLevel.push(node.val)

      // Add children for next level
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(currentLevel)
  }

  return result
}

// Example output: [[1], [2, 3], [4, 5]]
//
//       1         <- Level 0
//      / \
//     2   3       <- Level 1
//    / \
//   4   5         <- Level 2

When to Use Each Traversal

Common Interview Problems

Problem 1: Maximum Depth of Binary Tree

Question: Given a binary tree, find its maximum depth (the number of nodes along the longest path from root to a leaf).

// DFS Approach (postorder logic)
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0

  const leftDepth = maxDepth(root.left)
  const rightDepth = maxDepth(root.right)

  return Math.max(leftDepth, rightDepth) + 1
}

// BFS Approach (count levels)
function maxDepthBFS(root: TreeNode | null): number {
  if (!root) return 0

  let depth = 0
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    depth++

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }

  return depth
}

// Time: O(n), Space: O(h) for DFS, O(w) for BFS
// where h = height, w = max width

Problem 2: Same Tree

Question: Given two binary trees, write a function to check if they are structurally identical with the same node values.

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  // Both null - same
  if (!p && !q) return true

  // One null, one not - different
  if (!p || !q) return false

  // Values different - different
  if (p.val !== q.val) return false

  // Recursively check both subtrees
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

// Iterative approach using BFS
function isSameTreeBFS(p: TreeNode | null, q: TreeNode | null): boolean {
  const queue: (TreeNode | null)[] = [p, q]

  while (queue.length > 0) {
    const node1 = queue.shift()
    const node2 = queue.shift()

    if (!node1 && !node2) continue
    if (!node1 || !node2) return false
    if (node1.val !== node2.val) return false

    queue.push(node1.left, node2.left)
    queue.push(node1.right, node2.right)
  }

  return true
}

// Time: O(n), Space: O(h)

Problem 3: Invert Binary Tree

Question: Given the root of a binary tree, invert the tree (swap left and right children at every node) and return its root.

// Recursive (preorder style)
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null

  // Swap children
  const temp = root.left
  root.left = root.right
  root.right = temp

  // Recursively invert subtrees
  invertTree(root.left)
  invertTree(root.right)

  return root
}

// Iterative BFS
function invertTreeBFS(root: TreeNode | null): TreeNode | null {
  if (!root) return null

  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const node = queue.shift()!

    // Swap children
    const temp = node.left
    node.left = node.right
    node.right = temp

    if (node.left) queue.push(node.left)
    if (node.right) queue.push(node.right)
  }

  return root
}

//   Before:      After:
//      4           4
//     / \         / \
//    2   7       7   2
//   / \         / \
//  1   3       3   1

Problem 4: Binary Tree Level Order Traversal

Question: Given a binary tree, return the level order traversal of its nodes values (i.e., from left to right, level by level).

function levelOrderTraversal(root: TreeNode | null): number[][] {
  if (!root) return []

  const result: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      level.push(node.val)

      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

// Variant: Zigzag Level Order (alternate direction each level)
function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return []

  const result: number[][] = []
  const queue: TreeNode[] = [root]
  let leftToRight = true

  while (queue.length > 0) {
    const levelSize = queue.length
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!

      // Add to front or back based on direction
      if (leftToRight) {
        level.push(node.val)
      } else {
        level.unshift(node.val)
      }

      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
    leftToRight = !leftToRight
  }

  return result
}

Binary Search Tree (BST) Properties

A Binary Search Tree is a special binary tree where for every node: all values in the left subtree are less than the node value, and all values in the right subtree are greater than the node value.

// BST Search - O(log n) average, O(n) worst
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (!root) return null

  if (val === root.val) {
    return root
  } else if (val < root.val) {
    return searchBST(root.left, val)  // Go left
  } else {
    return searchBST(root.right, val) // Go right
  }
}

// Iterative version (more efficient - no call stack)
function searchBSTIterative(root: TreeNode | null, val: number): TreeNode | null {
  while (root && root.val !== val) {
    root = val < root.val ? root.left : root.right
  }
  return root
}

// Validate BST - use inorder property
function isValidBST(root: TreeNode | null): boolean {
  let prev = -Infinity

  function inorder(node: TreeNode | null): boolean {
    if (!node) return true

    // Check left subtree
    if (!inorder(node.left)) return false

    // Check current node (must be greater than previous)
    if (node.val <= prev) return false
    prev = node.val

    // Check right subtree
    return inorder(node.right)
  }

  return inorder(root)
}

// Kth Smallest Element in BST
function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0
  let result = 0

  function inorder(node: TreeNode | null) {
    if (!node || count >= k) return

    inorder(node.left)

    count++
    if (count === k) {
      result = node.val
      return
    }

    inorder(node.right)
  }

  inorder(root)
  return result
}

Time & Space Complexity Summary

Time Complexity: O(n) for all traversals - we visit each node exactly once
Space Complexity:

• Recursive DFS: O(h) where h is height (O(log n) balanced, O(n) worst)
• Iterative DFS: O(h) for the stack
• BFS: O(w) where w is maximum width (up to n/2 for complete tree)

Pro Tips for Interviews

• Start with recursion: It is cleaner and easier to get right. Mention you can do iterative if needed.
• Know the patterns: DFS uses stack (explicit or call stack), BFS uses queue
• BST insight: Inorder traversal gives sorted order - this unlocks many problems
• Edge cases: Empty tree, single node, skewed tree (linked list)
• Draw the tree: Visualize the traversal order with a simple example
• Return type matters: Some problems want void (modify in place), some want a new structure

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Maximum Depth (104), Same Tree (100), Invert Binary Tree (226), Symmetric Tree (101)
• Medium: Level Order Traversal (102), Validate BST (98), Kth Smallest in BST (230), Path Sum II (113)
• Hard: Binary Tree Maximum Path Sum (124), Serialize and Deserialize Binary Tree (297)

Continue Learning

• Binary Search Technique — Searching in sorted structures including BSTs
• Two Pointers Pattern — Another fundamental technique for arrays
• Big O Notation Explained — Understand traversal complexity analysis
• Start Practicing — Apply tree traversals to real interview problems