Suggest an edit

Improve this article

Refine the answer for “What are the main types of tree traversal?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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;
}

// 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts616 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.