Binary trees

What you'll learn

What a binary tree is, how a binary search tree keeps values in order, and how in-order, pre-order and level-order traversal visit nodes.

Why it matters

File systems, HTML pages (the DOM), databases and decision logic are all trees. Understanding trees is the doorway to graphs, heaps and many interview problems.

Explanation

A tree is made of nodes connected by edges, starting at one root. In a binary tree, each node has at most two children: left and right.

A binary search tree (BST) adds a rule: everything in a node's left subtree is smaller, everything in its right subtree is larger. That makes searching like binary search: go left or right at each node. For a balanced tree that is O(log n).

To traverse (visit every node) there are a few classic orders:

• In-order: left, node, right. On a BST this gives the values sorted.
• Pre-order: node, left, right.
• Post-order: left, right, node.
• Level-order: row by row, top to bottom.

Example

Step-by-step walkthrough

Visited: []

inorder traversal: left, then node, then right.

Play

1. 8 becomes the root. 3 is smaller so it goes left. 10 is larger so it goes right.
2. 1 and 6 go under 3; 14 goes under 10.
3. In-order visits the left subtree, then the node, then the right subtree.
4. That reads the values smallest to largest: [ 1, 3, 6, 8, 10, 14 ].

Compare with a level-order walk, which goes row by row:

Visited: []

level traversal: level by level, top to bottom.

Play

Try it yourself

Add a height(node) function that returns 0 for null and 1 + max(height(left), height(right)) otherwise.

Tree heightJavaScript

Editable codeclass TreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } function insert(root, value) { if (root === null) return new TreeNode(value); if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value); return root; } function height(node) { if (node === null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } let root = null; for (const v of [8, 3, 10, 1, 6, 14]) root = insert(root, v); console.log("height:", height(root));

Run ResetCopyCtrl+Enter to run

Common mistakes

• Forgetting the base case node === null in recursive functions.
• Assuming every BST is balanced. Inserting sorted values makes a long chain, which is O(n) to search.
• Mixing up traversal orders. Only in-order gives sorted values on a BST.
• Duplicates. Decide on a rule (left or right) and stick to it.

Quick quiz

Summary

• A binary tree node has at most two children.
• A BST keeps smaller values left and larger values right, giving O(log n) search when balanced.
• In-order traversal of a BST yields sorted values.

You finished the DSA lessons available so far. Graphs, recursion and dynamic programming are coming next.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insert(root, value) {
  if (root === null) return new TreeNode(value);
  if (value < root.value) root.left = insert(root.left, value);
  else root.right = insert(root.right, value);
  return root;
}

function inOrder(node, out = []) {
  if (node === null) return out;
  inOrder(node.left, out);
  out.push(node.value);
  inOrder(node.right, out);
  return out;
}

let root = null;
for (const v of [8, 3, 10, 1, 6, 14]) {
  root = insert(root, v);
}
console.log(inOrder(root));