Trees

Common Tree Problems

Written by Swapnil RajaUpdated 29 Aug 2026

Nearly every tree question is post-order: solve both subtrees, then combine. Once you see that, the code stops being something you memorise.

Depth and diameter

Two answers from one traversal

javascript

function maxDepth(node) {
  if (!node) return 0
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right))
}

// Longest path between any two nodes — it need not pass through the root.
function diameter(root) {
  let best = 0

  function depth(node) {
    if (!node) return 0

    const left = depth(node.left)
    const right = depth(node.right)

    // The best path through this node.
    best = Math.max(best, left + right)

    // What this node reports upward.
    return 1 + Math.max(left, right)
  }

  depth(root)
  return best
}

const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } }
console.log(maxDepth(demoTree))  // 2
console.log(diameter(demoTree))  // 2

Diameter is the pattern worth studying: the function returns one thing and records another. The answer through a node is not the answer it reports to its parent.

Lowest common ancestor

LCA in a general binary tree

javascript

function lca(node, a, b) {
  if (!node || node === a || node === b) return node

  const left = lca(node.left, a, b)
  const right = lca(node.right, a, b)

  // Found one on each side — this node is the meeting point.
  if (left && right) return node

  // Otherwise pass up whichever side found something.
  return left || right
}

const demoLeft = { value: 2, left: null, right: null }
const demoRight = { value: 3, left: null, right: null }
const demoTree = { value: 1, left: demoLeft, right: demoRight }
console.log(lca(demoTree, demoLeft, demoRight).value)  // 1

In a binary search tree it is simpler still: descend left while both targets are smaller, right while both are larger, and the first node that splits them is the answer.

Path sums

Root to leaf

javascript

function hasPathSum(node, target) {
  if (!node) return false

  const remaining = target - node.value

  // A leaf — this is where the sum must land exactly.
  if (!node.left && !node.right) return remaining === 0

  return hasPathSum(node.left, remaining) || hasPathSum(node.right, remaining)
}

const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: null }
console.log(hasPathSum(demoTree, 3))  // true
console.log(hasPathSum(demoTree, 9))  // false

The leaf check is the part people get wrong. Returning remaining === 0 at any node counts partial paths that do not reach a leaf.

Symmetry

Mirror image

javascript

function isSymmetric(root) {
  if (!root) return true

  function mirror(a, b) {
    if (!a && !b) return true
    if (!a || !b) return false

    return a.value === b.value
        && mirror(a.left, b.right)   // outside pair
        && mirror(a.right, b.left)   // inside pair
  }

  return mirror(root.left, root.right)
}

const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 2, left: null, right: null } }
console.log(isSymmetric(demoTree))  // true

The crossed comparison is the whole thing - left against right, right against left. Comparing like for like tests whether the halves are identical, not mirrored.

The shape to internalise

Base case answers for null.
Recurse into both children before deciding anything.
Combine their answers with the current node.
If the answer at a node differs from what the parent needs, record one and return the other.

Most tree problems are one post-order pass

If a node's answer depends on its children, compute the children first and combine. Height, diameter, balanced-or-not, subtree sums and lowest common ancestor are all this shape, which is why they feel repetitive once you see it.

Diameter and balance in one pass each

javascript

// Longest path between any two nodes, measured in edges.
function diameter(root) {
  let best = 0

  function height(node) {
    if (!node) return 0
    const left = height(node.left)
    const right = height(node.right)
    best = Math.max(best, left + right)   // path through this node
    return 1 + Math.max(left, right)
  }

  height(root)
  return best
}

// -1 doubles as "not balanced", avoiding a second traversal.
function isBalanced(root) {
  function check(node) {
    if (!node) return 0
    const left = check(node.left)
    if (left === -1) return -1
    const right = check(node.right)
    if (right === -1) return -1
    if (Math.abs(left - right) > 1) return -1
    return 1 + Math.max(left, right)
  }

  return check(root) !== -1
}

const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } }
console.log(diameter(demoTree))    // 2
console.log(isBalanced(demoTree))  // true

Both compute a value for the caller while updating an answer on the way up. The sentinel -1 in isBalanced keeps it to a single traversal rather than calling height at every node, which would be O(n²).

Lowest common ancestor

In a plain binary tree: recurse both sides; if both return non-null, the current node is the answer. In a BST you can do better - walk down from the root, going left while both targets are smaller and right while both are larger. The first node that splits them is the ancestor, in O(height).

PreviousBinary Search Trees NextTries (Prefix Trees)