Binary tree

Overview

A binary tree is a hierarchy of nodes where each node has at most two children, left and right. The top node is the root, and nodes with no children are leaves. Trees represent hierarchical data and are the basis for search trees, heaps, tries, and expression trees.

Almost every binary tree problem is solved with recursion: define what the function returns for one node, handle the null case, and combine the answers from the left and right subtrees. The skill is choosing what information flows up (return values) and what flows down (parameters).

When to use it

• Data is hierarchical: folders, org charts, HTML DOM, expression parsing.
• The problem gives a TreeNode root.
• You need to reason about paths, depths, subtrees, or ancestors.
• The answer for a node depends on the answers for its children.

Problem patterns it solves

Where it is used in real software

Key terms

Root / leaf

The top node / a node with no children.

Height

Number of nodes (or edges) on the longest root-to-leaf path.

Depth

Distance from the root to a node.

Full / complete / perfect

Every node has 0 or 2 children / all levels full except the last, filled left to right / all levels completely full.

Subtree

A node together with all its descendants.

Solving tree problems recursively

1. 1
   Define the return value

   Example: height(node) returns the height of the subtree rooted at node.

2. 2
   Handle null

   height(null) = 0. The null case is the base case for almost every tree function.

3. 3
   Ask the children

   left = height(node.left), right = height(node.right). Trust the recursion.

4. 4
   Combine

   return 1 + max(left, right).

5. 5
   Use a global when the answer is not the return value

   Diameter returns height but updates a best variable with left + right at each node.

Diameter of a binary tree

Tree: 1 has children 2 and 3; 2 has children 4 and 5. Diameter = longest path in edges.

The diameter is 3 (path 4 - 2 - 1 - 3). The function returns height to its parent but records left + right as a candidate answer, a pattern you will reuse for maximum path sum.

Implementation

1class TreeNode {2  constructor(val, left = null, right = null) {3    this.val = val;4    this.left = left;5    this.right = right;6  }7}8 9const maxDepth = (node) => (node ? 1 + Math.max(maxDepth(node.left), maxDepth(node.right)) : 0);10 11function diameterOfBinaryTree(root) {12  let best = 0;13  function height(node) {14    if (!node) return 0;15    const left = height(node.left);16    const right = height(node.right);17    best = Math.max(best, left + right); // path passing through node18    return 1 + Math.max(left, right);19  }20  height(root);21  return best;22}23 24function isBalanced(root) {25  // returns -1 when unbalanced so we can stop early26  function check(node) {27    if (!node) return 0;28    const left = check(node.left);29    if (left === -1) return -1;30    const right = check(node.right);31    if (right === -1 || Math.abs(left - right) > 1) return -1;32    return 1 + Math.max(left, right);33  }34  return check(root) !== -1;35}36 37function lowestCommonAncestor(root, p, q) {38  if (!root || root === p || root === q) return root;39  const left = lowestCommonAncestor(root.left, p, q);40  const right = lowestCommonAncestor(root.right, p, q);41  if (left && right) return root; // p and q are on different sides42  return left ?? right;43}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Missing the null base case.

  Fix: Start every recursive tree function with if (!node) return base.

• Confusing height in nodes and in edges.

  Fix: State which one you use; diameter in edges is left + right when heights count nodes.

• Returning the wrong thing upward in path problems.

  Fix: A path can bend at a node but only one branch can continue to the parent.

Interview questions

Practice problems