DSABinary Trees

Binary Trees

A binary tree is a tree where every node has at most two children, called left and right. This constraint — simple as it sounds — unlocks a rich family of algorithms: efficient search (BST), instant min/max access (heap), expression evaluation, and dozens of the most popular interview problems. Mastering binary trees is non-negotiable for technical interviews.

The TreeNode class

Every binary tree problem starts here. The node holds a value and optional pointers to left and right children.

Binary tree node

JS
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val   = val
    this.left  = left
    this.right = right
  }
}

// Build the tree shown in examples below:
//         1
//        / \
//       2   3
//      / \   \
//     4   5   6
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
)
Varieties of binary trees

Variety

Definition

Key property

Full binary tree

Every node has 0 or 2 children — never 1.

Nodes = 2 × leaves - 1

Complete binary tree

All levels filled except possibly the last, which is filled left to right.

Can be stored in an array with no gaps; used by heaps.

Perfect binary tree

All internal nodes have exactly 2 children and all leaves are at the same depth.

Nodes = 2^(h+1) - 1; leaves = 2^h

Balanced binary tree

Height of left and right subtrees of every node differs by at most 1.

Guarantees O(log n) height and thus O(log n) operations.

Degenerate (skewed) tree

Every node has at most one child — essentially a linked list.

Height = n-1; all operations degrade to O(n).

Visual comparison

Text
Full:          Complete:       Perfect:        Degenerate:
    1              1               1                1
   / \            / \            /   \              \
  2   3          2   3          2     3              2
 / \            / \  /        / \   / \              \
4   5          4  5 6        4  5  6  7              3
                                                      \
                                                       4
Level-order properties

In a perfect binary tree with height h (0-indexed from the root):

  • Level k has exactly 2^k nodes.

  • Total nodes = 2^(h+1) - 1.

  • Number of leaves = 2^h (more than all internal nodes combined).

  • The last level holds ~50% of all nodes.

Node count by level

Text
Level 0:        1          →  1 node   (2^0)
Level 1:      2   3        →  2 nodes  (2^1)
Level 2:    4  5  6  7     →  4 nodes  (2^2)
Level 3:  8 9 ...          →  8 nodes  (2^3)

Total at height 3: 1+2+4+8 = 15 = 2^4 - 1
Counting nodes

Count all nodes — O(n) time, O(h) space

JS
function countNodes(root) {
  if (!root) return 0
  return 1 + countNodes(root.left) + countNodes(root.right)
}

// For a COMPLETE binary tree we can do better: O(log^2 n)
function countNodesComplete(root) {
  if (!root) return 0

  let leftHeight = 0, rightHeight = 0
  let l = root, r = root

  while (l) { leftHeight++;  l = l.left  }
  while (r) { rightHeight++; r = r.right }

  // If left and right heights match, the tree is perfect
  if (leftHeight === rightHeight) return (1 << leftHeight) - 1

  return 1 + countNodesComplete(root.left) + countNodesComplete(root.right)
}
Height of a binary tree

Height = number of edges on the longest root-to-leaf path. An empty tree has height -1; a single node has height 0.

Height — O(n) time, O(h) space

JS
function height(root) {
  if (!root) return -1
  return 1 + Math.max(height(root.left), height(root.right))
}

// Minimum depth: distance to the nearest leaf (not the farthest)
// BFS is usually better here — it exits as soon as it finds a leaf
function minDepth(root) {
  if (!root) return 0
  if (!root.left && !root.right) return 1        // leaf

  // If only one side exists, go that way (don't count the null child)
  if (!root.left)  return 1 + minDepth(root.right)
  if (!root.right) return 1 + minDepth(root.left)

  return 1 + Math.min(minDepth(root.left), minDepth(root.right))
}
Diameter of a binary tree

The diameter (or width) is the length of the longest path between any two nodes. The path may or may not pass through the root. At every node, the longest path through that node is height(left) + height(right) + 2 (counting edges). Track the global maximum during a post-order DFS.

Diameter through node 2

Text
           1
          / \
         2   3
        / \
       4   5

  Diameter passing through 2:
    height(left of 2)  = 0  (node 4)
    height(right of 2) = 0  (node 5)
    path = 0 + 0 + 2 = 2  ← edges: 4→2→5

  Diameter passing through 1:
    height(left of 1)  = 1  (subtree rooted at 2)
    height(right of 1) = 0  (node 3)
    path = 1 + 0 + 2 = 3  ← edges: 4→2→1→3  (or 5→2→1→3)

  Answer: 3

Diameter — O(n) with a single DFS

JS
function diameterOfBinaryTree(root) {
  let maxDiameter = 0

  function dfs(node) {
    if (!node) return -1                        // height of null = -1
    const left  = dfs(node.left)
    const right = dfs(node.right)
    // path through this node (in edges): (left+1) + (right+1)
    maxDiameter = Math.max(maxDiameter, left + right + 2)
    return 1 + Math.max(left, right)            // return height
  }

  dfs(root)
  return maxDiameter
}
Note
Returning height from the recursive function while updating a global maximum is the canonical pattern for diameter, maximum path sum, and similar "bottom-up" tree problems.
Maximum path sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge, and no node appears twice. The path does not need to pass through the root. Find the path with the maximum sum of node values.

Maximum path sum — O(n)

JS
function maxPathSum(root) {
  let globalMax = -Infinity

  // Returns the maximum gain we can get going DOWN from node
  // (we can only extend the path downward, not branch left AND right
  //  at the same time when returning to the parent)
  function gain(node) {
    if (!node) return 0

    // Ignore negative subtrees (contribute 0 if negative)
    const leftGain  = Math.max(gain(node.left),  0)
    const rightGain = Math.max(gain(node.right), 0)

    // A path can go left → node → right (doesn't need to continue up)
    globalMax = Math.max(globalMax, node.val + leftGain + rightGain)

    // But we can only pick one direction to return to the parent
    return node.val + Math.max(leftGain, rightGain)
  }

  gain(root)
  return globalMax
}

// Example: [-10, 9, 20, null, null, 15, 7]
//         -10
//         /  \
//        9   20
//           /  \
//          15   7
// Best path: 15 → 20 → 7 = 42
console.log(maxPathSum(
  new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
  )
)) // 42
Symmetric tree

A binary tree is symmetric (a mirror of itself) if the left subtree is a mirror reflection of the right subtree.

Text
  Symmetric:          Not symmetric:
       1                    1
      / \                  / \
     2   2                2   2
    / \ / \                \   \
   3  4 4  3               3   3

Symmetric tree — O(n)

JS
function isSymmetric(root) {
  function isMirror(left, right) {
    if (!left && !right) return true    // both null: symmetric
    if (!left || !right) return false   // one null, one not: asymmetric
    return (
      left.val === right.val &&
      isMirror(left.left,  right.right) &&
      isMirror(left.right, right.left)
    )
  }
  return isMirror(root?.left, root?.right)
}

// Iterative version using a queue (pairs of nodes to compare)
function isSymmetricIterative(root) {
  const queue = [root?.left, root?.right]
  while (queue.length) {
    const left  = queue.shift()
    const right = queue.shift()
    if (!left && !right) continue
    if (!left || !right || left.val !== right.val) return false
    queue.push(left.left,  right.right)
    queue.push(left.right, right.left)
  }
  return true
}
Invert a binary tree

Swapping the left and right child of every node produces the mirror image of the tree. This is a classic DFS problem — do it recursively (post-order) or iteratively (BFS).

Text
  Before:          After:
       4                4
      / \              / \
     2   7            7   2
    / \ / \          / \ / \
   1  3 6  9        9  6 3  1

Invert binary tree — O(n)

JS
// Recursive — clean and natural
function invertTree(root) {
  if (!root) return null
  ;[root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
  return root
}

// Iterative BFS
function invertTreeBFS(root) {
  if (!root) return null
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    ;[node.left, node.right] = [node.right, node.left]
    if (node.left)  queue.push(node.left)
    if (node.right) queue.push(node.right)
  }
  return root
}
Balanced binary tree check

A tree is height-balanced if, for every node, the heights of the left and right subtrees differ by no more than 1. A naive two-pass approach is O(n log n); the optimal single-pass approach returns -1 as a sentinel for "unbalanced."

Balanced check — O(n) single pass

JS
function isBalanced(root) {
  // Returns height if balanced, -2 as sentinel if unbalanced
  function checkHeight(node) {
    if (!node) return -1                // empty subtree: height -1

    const left = checkHeight(node.left)
    if (left === -2) return -2          // left unbalanced — short-circuit

    const right = checkHeight(node.right)
    if (right === -2) return -2         // right unbalanced

    if (Math.abs(left - right) > 1) return -2   // this node unbalanced

    return 1 + Math.max(left, right)    // balanced: return height
  }

  return checkHeight(root) !== -2
}
Lowest common ancestor (LCA)

The LCA of two nodes p and q is the deepest node that is an ancestor of both. For a general binary tree (not a BST), the key insight is: if p and q are found in different subtrees of a node, that node is the LCA.

LCA of binary tree — O(n)

JS
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root

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

  // p and q are in different subtrees → root is LCA
  if (left && right) return root

  // Both in same subtree → recurse returned the answer already
  return left ?? right
}

// For a BST we can do better — use BST property:
function lcaBST(root, p, q) {
  while (root) {
    if (p.val < root.val && q.val < root.val) root = root.left
    else if (p.val > root.val && q.val > root.val) root = root.right
    else return root   // split point: root is LCA
  }
  return null
}
Serialise and deserialise a binary tree

Convert a binary tree to a string (and back) so it can be stored or transmitted. Pre-order DFS with null sentinels is the simplest approach and handles any shape of tree.

Serialise / deserialise — O(n)

JS
function serialize(root) {
  const parts = []
  function dfs(node) {
    if (!node) { parts.push('N'); return }
    parts.push(String(node.val))
    dfs(node.left)
    dfs(node.right)
  }
  dfs(root)
  return parts.join(',')
}
// Example: "1,2,4,N,N,5,N,N,3,N,6,N,N"

function deserialize(data) {
  const vals = data.split(',')
  let i = 0
  function dfs() {
    if (vals[i] === 'N') { i++; return null }
    const node = new TreeNode(Number(vals[i++]))
    node.left  = dfs()
    node.right = dfs()
    return node
  }
  return dfs()
}
Level order traversal (BFS)

Return each level as its own array. This is the foundation for problems like "right side view," "average of levels," and "zigzag traversal."

Level order — O(n)

JS
function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue  = [root]

  while (queue.length) {
    const levelSize = queue.length     // snapshot before we enqueue children
    const level = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left)  queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

// Right side view: last element of each level
function rightSideView(root) {
  return levelOrder(root).map(level => level[level.length - 1])
}

// Zigzag (snake) level order
function zigzagLevelOrder(root) {
  let leftToRight = true
  return levelOrder(root).map(level => {
    const row = leftToRight ? level : [...level].reverse()
    leftToRight = !leftToRight
    return row
  })
}
Path sum problems

Has path sum / all root-to-leaf paths — O(n)

JS
// Does any root-to-leaf path sum to target?
function hasPathSum(root, target) {
  if (!root) return false
  if (!root.left && !root.right) return root.val === target   // leaf
  const remain = target - root.val
  return hasPathSum(root.left, remain) || hasPathSum(root.right, remain)
}

// Return all root-to-leaf paths that sum to target
function pathSum(root, target) {
  const result = []

  function dfs(node, remaining, path) {
    if (!node) return
    path.push(node.val)
    if (!node.left && !node.right && remaining === node.val) {
      result.push([...path])            // found a valid path
    }
    dfs(node.left,  remaining - node.val, path)
    dfs(node.right, remaining - node.val, path)
    path.pop()                          // backtrack
  }

  dfs(root, target, [])
  return result
}
Complexity summary

Operation

Time

Space (call stack)

Notes

DFS traversal (any order)

O(n)

O(h)

h = height; O(log n) balanced, O(n) skewed

BFS / level order

O(n)

O(w)

w = max width ≈ n/2 at last level

Height

O(n)

O(h)

Count nodes

O(n)

O(h)

O(log² n) for complete binary tree

Diameter

O(n)

O(h)

Single post-order DFS

Max path sum

O(n)

O(h)

Single post-order DFS

LCA

O(n)

O(h)

O(log n) for BST

Symmetric check

O(n)

O(h)

Invert

O(n)

O(h)

Serialise / deserialise

O(n)

O(n)

O(n) output string

Top interview problems

  1. Maximum depth — simple post-order; height(root) + 1.

  2. Minimum depth — BFS stops at the first leaf (faster than DFS).

  3. Path sum I / II / III — DFS with a running sum; path sum III uses prefix sums.

  4. Symmetric tree — recursive or iterative mirror check.

  5. Invert binary tree — swap left/right recursively.

  6. Diameter — post-order tracking global max of left + right heights.

  7. Maximum path sum — post-order with negative gain pruning.

  8. LCA — post-order; return the node when both p and q found.

  9. Serialise / deserialise — pre-order DFS with null sentinels.

  10. Right side view — BFS, take last element of each level.

  11. Binary tree cameras — greedy post-order, parent covers leaf.

  12. Count complete tree nodes — binary search on last level in O(log² n).

Tip
In a post-order recursion, you process children before the current node. Most "compute something for a node from its subtrees" problems (height, diameter, path sum, balance check) are post-order at heart — if you find yourself calling a helper twice per node, merge it into a single post-order pass.
Warning
A common mistake in path sum problems: only mark a path complete when you reach a **leaf** (no children), not when you reach `null`. Otherwise a node with one child would incorrectly count the null child as a valid path endpoint.