Trees and Binary Search Trees Explained

A tree is a hierarchy of nodes connected from a single root, and a binary search tree (BST) is a tree that keeps its values ordered so you can search in O(log n). Trees model anything hierarchical — file systems, the HTML DOM, org charts — and they’re a major coding-interview topic because they reward clean recursion.

Get the vocabulary, the BST property, and the three traversals down, and most tree problems become short recursive functions.

Tree vocabulary

• Root — the top node, with no parent.
• Child / parent — nodes directly below / above.
• Leaf — a node with no children.
• Height — the longest path from a node down to a leaf.
• Binary tree — every node has at most two children (left, right).

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

The binary search tree property

A BST adds one rule that changes everything: for every node, left subtree < node < right subtree.

        8
       / \
      3   10
     / \    \
    1   6    14

That ordering means searching is like binary search — at each node you go left or right, halving what’s left:

function search(node, target) {
  if (!node) return null;
  if (target === node.value) return node;
  return target < node.value
    ? search(node.left, target)    // go left
    : search(node.right, target);  // go right
}

When the tree is balanced, that’s O(log n) — the whole reason BSTs exist.

The three traversals (depth-first)

Visiting every node has three recursive orders, and which you choose matters:

function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  visit(node.value);        // left → NODE → right
  inOrder(node.right);
}

The killer fact: in-order traversal of a BST yields sorted values. Many “is this a valid BST?” and “kth smallest” problems lean on it.

Level-order traversal (breadth-first)

To visit level by level instead of depth-first, use a queue — this is BFS on a tree:

function levelOrder(root) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    visit(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

Reach for level-order when the problem mentions levels, depth, or “closest” nodes.

Balanced vs unbalanced

A BST’s O(log n) promise assumes it’s balanced. Insert already-sorted data into a naive BST and every node goes right, producing a straight line — a glorified linked list with O(n) operations.

1
 \
  2
   \
    3      ← inserting 1,2,3 in order: degenerate, O(n)

Production libraries use self-balancing trees (AVL, red-black) that rotate on insertion to stay balanced. You rarely implement these in an interview, but you should know why they exist.

Common interview problems

• Validate a BST — in-order traversal must be strictly increasing.
• Maximum depth / height — classic recursion.
• Lowest common ancestor — walk down comparing values (in a BST) or recurse.
• Level-order / zigzag traversal — BFS with a queue.
• Invert a binary tree — swap every node’s children recursively.

Common mistakes

• Forgetting the base case (if (!node) return) → null errors or infinite recursion. See recursion.
• Confusing tree height with node count.
• Assuming a binary tree is a BST — only a BST has the ordering; a general binary tree doesn’t.
• Validating a BST by only checking immediate children — you must enforce the range constraint down the whole subtree.

Where this fits

Trees are Phase 2 of the coding interview roadmap, built directly on recursion and leading into graphs (a tree is a special graph).

The traversals, BST operations, and recursive templates are drawn out as diagrams in our job-ready tier — JavaScript in Three Months, Python in Three Months, and Java in Three Months. For self-balancing trees, tries, heaps, and segment trees that appear in senior interviews, the for Staff Engineers tier goes deeper: JavaScript, Python, Java.

Think “solve it for the subtrees, then combine,” and trees become the friendliest recursion practice there is.