What are the main types of tree traversal?

AlgorithmsJunior~1 min read

Short answer

DFS (depth-first search):
- Preorder (NLR)
- Inorder (LNR) - defined for binary trees
- Postorder (LRN)
BFS (breadth-first search): Level-order

Detailed answer

Classification of traversals

DFS (Depth-First Search)
- Preorder (NLR): node first, then the left subtree, then the right.
- Inorder (LNR): left subtree, node, right subtree. Applies to binary trees; for a BST it gives a sorted sequence.
- Postorder (LRN): left subtree, right subtree, then the node.
BFS (Breadth-First Search)
- Level-order: visiting nodes layer by layer, top to bottom, left to right.

Complexity and memory

Time: all of the listed traversals visit each node exactly once, O(n).
Memory: DFS is O(h), where h is the tree's height (the recursion stack or an explicit stack; O(n) in the worst case). BFS is O(w), where w is the maximum level width (O(n) in the worst case).

Recursive examples (JavaScript)

javascript

// Binary tree nodes
class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// DFS (recursive)
function preorder(node, res = []) { // NLR
  if (!node) return res;
  res.push(node.val);
  preorder(node.left, res);
  preorder(node.right, res);
  return res;
}

function inorder(node, res = []) { // LNR (for binary trees)
  if (!node) return res;
  inorder(node.left, res);
  res.push(node.val);
  inorder(node.right, res);
  return res;
}

function postorder(node, res = []) { // LRN
  if (!node) return res;
  postorder(node.left, res);
  postorder(node.right, res);
  res.push(node.val);
  return res;
}

// BFS (level-order)
function bfs(root) {
  const res = [];
  if (!root) return res;
  const q = [root];
  while (q.length) {
    const node = q.shift();
    res.push(node.val);
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return res;
}

Iterative examples (JavaScript)

javascript

function preorderIter(root) {
  const res = [];
  if (!root) return res;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

function inorderIter(root) {
  const res = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
}

function postorderIter(root) {
  const res = [];
  if (!root) return res;
  const s1 = [root];
  const s2 = [];
  while (s1.length) {
    const node = s1.pop();
    s2.push(node);
    if (node.left) s1.push(node.left);
    if (node.right) s1.push(node.right);
  }
  while (s2.length) {
    res.push(s2.pop().val);
  }
  return res;
}

// BFS (level-order)
function bfsIter(root) {
  return bfs(root);
}

Example tree and traversal results

javascript

const root =
  new Node(1,
    new Node(2,
      new Node(4),
      new Node(5)
    ),
    new Node(3,
      null,
      new Node(6)
    )
  );

/*
    1
   / \
  2   3
 / \   \
4   5   6
*/

console.log('Preorder (NLR):', preorder(root));   // [1, 2, 4, 5, 3, 6]
console.log('Inorder (LNR):', inorder(root));     // [4, 2, 5, 1, 3, 6]
console.log('Postorder (LRN):', postorder(root)); // [4, 5, 2, 6, 3, 1]
console.log('BFS (level-order):', bfs(root));     // [1, 2, 3, 4, 5, 6]

When to use which traversal

Preorder: copying/serializing a tree, generating the prefix notation of expressions.
Inorder (for binary trees): getting a sorted list from a BST, checking BST properties.
Postorder: deleting/freeing a tree (bottom-up), evaluating expressions (postfix notation).
BFS (level-order): finding the shortest path by edge count in unweighted trees/graphs, level-based problems (per-level averages, right/left side views, and so on).

Notes and pitfalls

Inorder is well-defined only for binary trees; for a general k-ary tree its analog depends on convention.
Recursion can overflow the stack on heavily unbalanced trees; use the iterative variants.
Memory optimizations exist, such as Morris traversal for inorder with O(1) extra memory, but it modifies links during the traversal.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.