Typorithm · easy

Binary Tree Traversals

binary-tree-traversalstreesdfsvisit-orderrecursion

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Binary Tree Traversals

Trees

Three DFS orders differ only by WHERE you record the node: before, between, or after recursing into the children.

All three traversals recurse left then right; only the position of the push changes.

Pre-order records the node first (top-down), in-order between the children (sorted for a BST), post-order last (bottom-up).

The shared skeleton makes the visit position the single distinguishing idea.

Pre: self, left, right.

In: left, self, right.

Post: left, right, self.

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

function preorder(root, result = []) {
  if (root === null) {
    return result;
  }
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

function postorder(root, result = []) {
  if (root === null) {
    return result;
  }
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);
  return result;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. In-order: left, self, right

Visiting self between the children yields sorted order for a BST.

inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result)

2. Pre-order: self first

Recording the node before its children captures structure top-down.

result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result)

3. Post-order: self last

Recording the node after its children processes leaves first.

postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.