Binary Trees and Tree Vocabulary

Trees are the data structure this course spends the most time on, because they're not a niche interview topic for frontend work — the DOM itself is a tree, and a large share of "reshape this data for the UI" problems (nested comments, file explorers, org charts) are secretly tree problems wearing other names. This lesson sets up the vocabulary everything after it leans on.

The shape and the words for it

A tree is a set of nodes connected so that there's exactly one path between any two of them, and one designated node — the root — that everything else descends from.

const tree = {
  value: "root",
  children: [
    { value: "A", children: [
      { value: "A1", children: [] },
      { value: "A2", children: [] },
    ]},
    { value: "B", children: [
      { value: "B1", children: [] },
    ]},
  ],
};

• Root — the single top node with no parent ("root" above).
• Parent / child — a direct connection one level apart ("root" is the parent of "A" and "B"; they are its children).
• Leaf — a node with no children ("A1", "A2", "B1" above).
• Depth (of a node) — how many steps up to the root. "root" has depth 0; "A" and "B" have depth 1; "A1", "A2", "B1" have depth 2.
• Height (of the tree) — the depth of its deepest node. This example tree has height 2.
• Subtree — any node, together with all of its descendants, treated as a tree in its own right. "A" and everything under it is a subtree of the whole.

A binary tree restricts every node to at most two children, conventionally called left and right:

const binaryNode = {
  value: 10,
  left: { value: 5, left: null, right: null },
  right: { value: 15, left: null, right: null },
};

Binary search trees: the ordering property that makes search fast

A binary search tree (BST) adds one rule on top of "at most two children": at every node, everything in its left subtree is smaller than the node's own value, and everything in its right subtree is larger.

function insert(node, value) {
  if (node === null) return { value, left: null, right: null };
  if (value < node.value) node.left = insert(node.left, value);
  else node.right = insert(node.right, value);
  return node;
}
 
function search(node, target) {
  if (node === null) return false;
  if (node.value === target) return true;
  return target < node.value ? search(node.left, target) : search(node.right, target);
}

This ordering is what makes search fast: at every node, comparing the target to the node's value tells you which entire subtree the target must be in, if it exists at all — the other whole subtree can be discarded without looking at a single node inside it. That's the same "halve the remaining possibilities" idea behind binary search on a sorted array (a later lesson), and it's why a balanced BST supports search in O(log n): each comparison eliminates roughly half of what's left, so the depth you need to descend to find (or rule out) any value is only log₂(n).

The promise that can quietly break: balance

That O(log n) claim has a condition attached, and it's the single most important thing to know about BSTs going in: it only holds if the tree is balanced — roughly the same depth on every path from root to leaf.

Insert already-sorted data (1, 2, 3, 4, 5, ...) into the insert function above, and watch what happens: every new value is larger than everything before it, so it always becomes the right child of the previous largest node. The result isn't a tree in any useful sense — it's a straight chain, identical in shape (and identical in search cost) to a linked list. Search degrades from the promised O(log n) to O(n) in this worst case, silently, with no error and no warning — the code is completely correct, and the shape of your input data is what determines whether you get the fast case or the slow one.

Self-balancing variants (AVL trees, red-black trees) exist specifically to guarantee height stays logarithmic regardless of insertion order — genuinely out of scope for a frontend-interview-focused course, but worth knowing they exist as the answer to "then how do real databases and language runtimes avoid this problem."

One more distinction worth locking in now: visiting every node (a full traversal, covered properly next lesson) is always O(n), regardless of shape or balance — there's no way to touch n things in fewer than n steps. The O(log n) promise is specifically about searching for one value, not about walking the whole tree.

What to remember

• Depth is per-node (distance from the root); height is per-tree (the deepest node's depth) — don't conflate the two.
• A binary search tree's ordering property — left subtree smaller, right subtree larger, at every node — is what lets search discard an entire subtree per comparison.
• A BST's O(log n) search promise depends on the tree staying roughly balanced; sorted-order insertion degenerates it into a chain with O(n) search, silently, with no error to warn you.
• Visiting every node in a tree is always O(n), regardless of balance — the O(log n) claim is specifically about searching, not about full traversal.