Tree problems in depth

Building a tree back from its traversals

Given pre-order and in-order sequences, you can reconstruct the exact original tree — this works because pre-order's first element is always the root, and once you know the root, in-order tells you exactly which values belong in the left subtree (everything before the root) versus the right subtree (everything after it).

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;

  const rootVal = preorder[0];
  const root = { val: rootVal, left: null, right: null };

  const splitIndex = inorder.indexOf(rootVal);
  const leftInorder = inorder.slice(0, splitIndex);
  const rightInorder = inorder.slice(splitIndex + 1);

  root.left = buildTree(preorder.slice(1, 1 + leftInorder.length), leftInorder);
  root.right = buildTree(preorder.slice(1 + leftInorder.length), rightInorder);

  return root;
}

Lowest Common Ancestor (LCA)

The LCA of two nodes is the deepest node that has both as descendants. On a plain binary tree, you find it by searching both subtrees and noticing where the paths to each target first "meet."

function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root; // p and q split across both sides — root is the LCA
  return left ?? right;            // both on one side — pass that answer up
}

On a BST specifically, you can skip the full search: compare both targets against the current node's value. If both are smaller, go left; if both are bigger, go right; the moment they split (or match the node), you've found the LCA in O(log n) instead of O(n) — the BST property does the pruning for you.

Checking if a tree is height-balanced

function isBalanced(root) {
  function check(node) {
    if (node === null) return 0; // height of an empty tree

    const leftHeight = check(node.left);
    if (leftHeight === -1) return -1; // already unbalanced below — stop early

    const rightHeight = check(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) return -1; // -1 means "unbalanced"

    return 1 + Math.max(leftHeight, rightHeight);
  }
  return check(root) !== -1;
}

Validate BST — the trap almost everyone falls into first

// pass down a valid (min, max) RANGE, tightened at every step
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;
  if (node.val <= min || node.val >= max) return false;

  return (
    isValidBST(node.left, min, node.val) &&   // left subtree must stay BELOW node.val
    isValidBST(node.right, node.val, max)      // right subtree must stay ABOVE node.val
  );
}

An equally valid alternative: run an in-order traversal and check the output is strictly increasing — since in-order on a real BST always produces sorted output (from the Trees chapter), any violation of that proves it isn't one. Both approaches are O(n) time, O(h) space.

Diameter of a binary tree

The diameter is the length of the longest path between any two nodes — and that path doesn't have to pass through the root. The subtlety: the longest path through a given node is leftHeight + rightHeight, but the final answer is the maximum of that value across every node, not just the root.

function diameterOfBinaryTree(root) {
  let diameter = 0;

  function height(node) {
    if (node === null) return 0;
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);

    diameter = Math.max(diameter, leftHeight + rightHeight); // update global answer at EVERY node

    return 1 + Math.max(leftHeight, rightHeight); // but only return height upward
  }

  height(root);
  return diameter;
}

This is the same shape as isBalanced above — a single post-order pass that computes a per-node value (height) while side-effecting a running global answer. That combination — "return one thing up the call stack, but also track a separate best-so-far as you go" — is worth recognizing as its own recurring template; it also solves Binary Tree Maximum Path Sum with the same shape (track the best path found anywhere, but only return the best single-branch extension upward, since a path can't fork twice).

Serialization — turning a tree into a string and back

Pre-order with explicit null markers is the standard approach — it's the only single traversal that, alone, can rebuild the exact tree shape without needing a second traversal like the construction problem above.

function serialize(root) {
  if (root === null) return "null";
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const values = data.split(",");
  let i = 0;

  function build() {
    if (values[i] === "null") { i++; return null; }
    const node = { val: Number(values[i++]), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

The null markers are what make one traversal enough — they tell the rebuilder exactly where each branch ends, instead of needing a second traversal to disambiguate the shape.

Recognizing which of these four you need

• "Given two traversals, rebuild the tree" → construction (use pre/post-order for the root, in-order to split subtrees)
• "Find the common ancestor" → LCA (BST property prunes it to O(log n) if it's a BST)
• "Is this tree balanced/valid?" → compute the property bottom-up in one pass, short-circuit on failure
• "Save this tree to a file / send over a network" → serialize with pre-order + null markers