Tree Traversals (DFS, BFS) — DSA

Tree Traversals (DFS & BFS)

A tree traversal visits every node exactly once in a defined order. The order you visit nodes determines what you can compute — picking the wrong traversal is one of the most common interview mistakes. Two families exist: Depth-First Search (DFS) dives deep before backtracking, and Breadth-First Search (BFS) sweeps level by level.

The Binary Tree Node

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val   = val
    this.left  = left
    this.right = right
  }
}

// Build the example tree used throughout this page:
//
//         1
//        / \
//       2   3
//      / \ / \
//     4  5 6  7
//
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, new TreeNode(6), new TreeNode(7))
)

1. Preorder Traversal — Root → Left → Right

Visit the root first, then recurse left, then right. Useful for copying/cloning a tree and for prefix-expression evaluation.

Visit order on the example tree

Text

         1          <- visit 1 first
        / \
       2   3         <- visit 2, then later 3
      / \ / \
     4  5 6  7       <- visit 4, 5, 6, 7

Preorder: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

Recursive preorder

function preorder(node, result = []) {
  if (!node) return result
  result.push(node.val)        // ROOT
  preorder(node.left,  result) // LEFT
  preorder(node.right, result) // RIGHT
  return result
}

preorder(root) // [1, 2, 4, 5, 3, 6, 7]

Iterative preorder — explicit stack

function preorderIterative(root) {
  if (!root) return []
  const result = []
  const stack  = [root]

  while (stack.length) {
    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
}
// [1, 2, 4, 5, 3, 6, 7]

2. Inorder Traversal — Left → Root → Right

Recurse left, visit root, recurse right. On a Binary Search Tree this produces a sorted sequence — the single most important property of inorder traversal in interviews.

Visit order on the example tree

Text

Inorder: 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

Recursive inorder

function inorder(node, result = []) {
  if (!node) return result
  inorder(node.left,  result) // LEFT
  result.push(node.val)       // ROOT
  inorder(node.right, result) // RIGHT
  return result
}

inorder(root) // [4, 2, 5, 1, 6, 3, 7]

Iterative inorder — explicit stack

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

  while (cur || stack.length) {
    // Reach the leftmost node
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    cur = stack.pop()
    result.push(cur.val) // visit
    cur = cur.right      // move to right subtree
  }
  return result
}
// [4, 2, 5, 1, 6, 3, 7]

3. Postorder Traversal — Left → Right → Root

Children before parent. Ideal when a node depends on the results of its subtrees — directory-size calculation, tree deletion, and postfix expression evaluation all follow this pattern.

Visit order on the example tree

Text

Postorder: 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

Recursive postorder

function postorder(node, result = []) {
  if (!node) return result
  postorder(node.left,  result) // LEFT
  postorder(node.right, result) // RIGHT
  result.push(node.val)         // ROOT
  return result
}

postorder(root) // [4, 5, 2, 6, 7, 3, 1]

Iterative postorder — reverse-preorder trick

function postorderIterative(root) {
  if (!root) return []
  const result = []
  const stack  = [root]

  while (stack.length) {
    const node = stack.pop()
    result.push(node.val)       // collect in reverse order
    if (node.left)  stack.push(node.left)
    if (node.right) stack.push(node.right)
  }
  return result.reverse()       // reverse gives L -> R -> Root
}
// [4, 5, 2, 6, 7, 3, 1]

4. Level Order Traversal (BFS)

Process all nodes at depth 0, then depth 1, then depth 2, and so on. A queue (FIFO) replaces the stack: enqueue the root, then for each node dequeued, enqueue its children.

Level-by-level visit order

Text

Level 0:  1
Level 1:  2   3
Level 2:  4  5  6  7

BFS output: [[1], [2, 3], [4, 5, 6, 7]]

Level order — returns array of levels

function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue  = [root]

  while (queue.length) {
    const levelSize = queue.length
    const level = []

    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
}

levelOrder(root)
// [[1], [2, 3], [4, 5, 6, 7]]

Tip

Use a proper queue or a two-pointer index into an array for O(1) dequeue. Array.shift() is O(n) — fine for interviews but swap it for a deque in production.

5. Morris Traversal — O(1) Space Inorder

All stack-based traversals use O(h) space. Morris traversal achieves O(1) space by temporarily threading the tree — it links each node's inorder predecessor back to that node, uses the link to return without a stack, then restores the original structure.

Threading concept

Text

Before:              After threading node 2 (first visit):
    2                       2
   / \                     / \
  1   3                   1   3
                           \
                            2  <- temporary back-link
                               (rightmost of left subtree -> cur)

Morris inorder traversal

function morrisInorder(root) {
  const result = []
  let cur = root

  while (cur) {
    if (!cur.left) {
      // No left subtree — visit and move right
      result.push(cur.val)
      cur = cur.right
    } else {
      // Find inorder predecessor: rightmost node of left subtree
      let pred = cur.left
      while (pred.right && pred.right !== cur) {
        pred = pred.right
      }

      if (!pred.right) {
        // First visit: create thread, go left
        pred.right = cur
        cur = cur.left
      } else {
        // Second visit: remove thread, visit, go right
        pred.right = null
        result.push(cur.val)
        cur = cur.right
      }
    }
  }
  return result
}
// Time: O(n)   Space: O(1)

Warning

Morris traversal temporarily mutates the tree. Never use it on a tree that may be read concurrently by another thread without proper locking.

Complexity Summary

Traversal	Time	Space (recursive)	Space (iterative)
Preorder	O(n)	O(h)	O(h)
Inorder	O(n)	O(h)	O(h)
Postorder	O(n)	O(h)	O(h)
Level Order	O(n)	O(w) max width	O(w)
Morris	O(n)	O(1)	O(1)

Note

h = height of tree. Balanced: O(log n). Skewed (degenerate): O(n). w = maximum width — O(n/2) = O(n) for a complete binary tree.

Applications of Each Traversal

Traversal	Classic applications
Preorder	Clone a tree, serialize/deserialize, prefix expression evaluation
Inorder	Sorted output from BST, kth smallest element, BST validation
Postorder	Delete a tree, compute directory/subtree size, postfix expression, LCA
Level Order	Minimum depth, right-side view, zigzag traversal, connect level pointers
Morris	Space-constrained inorder, threaded binary trees

Interview Problem 1 — Right Side View

Return the last visible node at each level when the tree is viewed from the right.

function rightSideView(root) {
  if (!root) return []
  const result = []
  const queue  = [root]

  while (queue.length) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      if (i === size - 1) result.push(node.val) // last in level
      if (node.left)  queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
  return result
}
// Tree (1, 2-3, 4-5-6-7) -> [1, 3, 7]
// Time: O(n)  Space: O(w)

Interview Problem 2 — Maximum Depth

// DFS: depth = 1 + max(left depth, right depth)
function maxDepth(root) {
  if (!root) return 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

// BFS alternative — count levels
function maxDepthBFS(root) {
  if (!root) return 0
  let depth = 0
  const queue = [root]
  while (queue.length) {
    depth++
    const size = queue.length
    for (let i = 0; i < size; 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) DFS / O(w) BFS

Interview Problem 3 — Zigzag Level Order

Return level-order values but alternate direction on successive levels.

function zigzagLevelOrder(root) {
  if (!root) return []
  const result    = []
  const queue     = [root]
  let leftToRight = true

  while (queue.length) {
    const size  = queue.length
    const level = []
    for (let i = 0; i < size; 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(leftToRight ? level : [...level].reverse())
    leftToRight = !leftToRight
  }
  return result
}
// Tree (1, 2-3, 4-5-6-7) -> [[1], [3, 2], [4, 5, 6, 7]]

Interview Problem 4 — Serialize and Deserialize

Encode a binary tree to a string and rebuild it. Preorder with null markers is the cleanest approach.

const NULL_MARKER = '#'
const SEP = ','

function serialize(root) {
  const parts = []
  function dfs(node) {
    if (!node) { parts.push(NULL_MARKER); return }
    parts.push(String(node.val))
    dfs(node.left)
    dfs(node.right)
  }
  dfs(root)
  return parts.join(SEP)
}

function deserialize(data) {
  const tokens = data.split(SEP)
  let i = 0
  function build() {
    if (tokens[i] === NULL_MARKER) { i++; return null }
    const node = new TreeNode(Number(tokens[i++]))
    node.left  = build()
    node.right = build()
    return node
  }
  return build()
}
// serialize(root) -> "1,2,4,#,#,5,#,#,3,6,#,#,7,#,#"
// deserialize(str) -> original tree reconstructed

Quick Reference

Preorder — root first; use for cloning and serializing
Inorder — sorted output from BST; memorize the iterative stack version
Postorder — children before parent; use for deletion and size computation
Level order — queue-based BFS; required for any "level" or "layer" problem
Morris — O(1) space inorder; mutates tree temporarily, restore when done
All DFS traversals: time O(n), space O(h)
BFS: time O(n), space O(w) — up to O(n) for a complete binary tree