Algorithms from zero

Tree dynamic programming

Crux Return one piece of information up (height), track another in a side variable (diameter). Each node solves a subproblem and contributes to a global answer. Core idea: a single DFS pass, two pieces of information.

◷ 28 min

You have solved tree problems by asking both subtrees for a value and combining the answers. But what if the final answer is NOT the value you return? What if a node must return its height to the parent, but compute something else—like the longest path through it—and put that in a side variable? This is tree DP: a node’s recursive call answers one question (return up), while a global or side variable tracks another question (the actual answer). The classic example is the diameter of a binary tree—the longest path between any two nodes—where each node returns its height but tracks the longest path passing through it.

Goal

After this lesson you can implement recursive tree functions where the return value differs from the final answer, recognize and apply the tree DP pattern (postorder recursion + side variable), solve the diameter of a binary tree problem and trace it correctly, implement a height-balanced tree checker, predict and verify the time and space complexity of tree DP algorithms, and extend the pattern to variations (longest path sum, diameter in directed trees).

The idea

What is tree DP (dynamic programming on trees)?

Tree DP is a technique where a recursive tree function solves two problems at once:

The return value (sent up to the parent).
A side computation (tracked globally or in a mutable variable).

The key insight: the node’s recursive call returns one piece of information up, while a side variable (or global state) accumulates the final answer.

The pattern

function treeDp(node) {
  // Base case
  if (node is null) return baseValue;
  
  // Recurse on subtrees
  leftInfo = treeDp(node.left);
  rightInfo = treeDp(node.right);
  
  // Combine for return (sent up)
  returnValue = combine(leftInfo, rightInfo, node);
  
  // Update side answer (the global answer)
  globalAnswer = updateAnswer(globalAnswer, leftInfo, rightInfo, node);
  
  return returnValue;
}

At each node:

Recurse down to both subtrees (postorder).
Compute a return value that makes sense for the parent (e.g., height).
Update a side variable with the final answer (e.g., longest path).

Example: the diameter of a binary tree

The diameter of a binary tree is the longest path between any two nodes, measured in edges. This path may or may not pass through the root.

For each node, we ask: “What is the longest path passing through you?” The answer is the sum of the heights of the two subtrees plus 2 edges (one to each child), or zero if the node is a leaf.

But to answer that question for every node, we must return something different to the parent: the height of the subtree. So:

Return: height of the subtree.
Side variable: the longest path found so far (the diameter).

Diameter at a node

For a node with left subtree height lh and right subtree height rh:

The longest path through the node = lh + rh + 2 (in edges). (The +2 accounts for the edges from the node down to the immediate children.)
The height of the subtree rooted at the node = 1 + max(lh, rh).

Height convention

A leaf node (no children) has height 0. An empty subtree (null) has height -1. This makes the math work: a node with two null children returns 1 + max(-1, -1) = 0, which is correct for a leaf.

The code

Example 1: Diameter of a binary tree


      1
      function diameterOfBinaryTree(root) {
    

      2
      let maxDiameter = 0;
    

      3
       
    

      4
      function dfs(node) {
    

      5
        // Base case: empty subtree has height -1
    

      6
        if (node === null) return -1;
    

      7
        
    

      8
        // Recurse on both subtrees
    

      9
        const leftHeight = dfs(node.left);
    

      10
        const rightHeight = dfs(node.right);
    

      11
        
    

      12
        // Update the global answer:
    

      13
        // Longest path through this node (in edges)
    

      14
        const diameterThroughNode = leftHeight + rightHeight + 2;
    

      15
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
    

      16
        
    

      17
        // Return the height of this subtree (sent to parent)
    

      18
        return 1 + Math.max(leftHeight, rightHeight);
    

      19
      }
    

      20
       
    

      21
      dfs(root);
    

      22
      return maxDiameter;
    

      23
      }

L1 Function computes the diameter (longest path in edges) of the tree.
L2 Side variable: tracks the longest path found so far.
L5 Base case: an empty subtree has height -1 (makes the math clean).
L8 Recurse left: get the height of the left subtree.
L9 Recurse right: get the height of the right subtree.
L12 The longest path through THIS node is (left height) + (right height) + 2 edges.
L13 Update the side variable: remember the longest path seen anywhere in the tree.
L16 Return the height of this subtree (what the parent needs to solve its problem).

Example: For the tree:

Tree structure:

Node 1 is the root.
Node 1’s left subtree (rooted at 2) and right subtree (rooted at 3).
Node 2’s left subtree (rooted at 4, a leaf) and right subtree (rooted at 5, a leaf).

Heights (leaf = 0, null = -1):

Node 4 (leaf): height = 0
Node 5 (leaf): height = 0
Node 3 (leaf): height = 0
Node 2 (two children): height = 1 + max(0, 0) = 1
Node 1 (two children): height = 1 + max(1, 0) = 2

Diameters (longest path through each node):

Node 4: diameter = -1 + -1 + 2 = 0 (a leaf, path is just itself)
Node 5: diameter = -1 + -1 + 2 = 0 (a leaf, path is just itself)
Node 3: diameter = -1 + -1 + 2 = 0 (a leaf, path is just itself)
Node 2: diameter = 0 + 0 + 2 = 2 (path from 4 → 2 → 5 is 2 edges)
Node 1: diameter = 1 + 0 + 2 = 3 (path from 4 → 2 → 1 → 3 is 3 edges)

The longest path in the entire tree is 3 edges: 4 → 2 → 1 → 3.

Example 2: Height-balanced binary tree

A tree is height-balanced if for every node, the heights of the left and right subtrees differ by at most 1. We can check this with tree DP: return the height if balanced, or -1 as a sentinel for “unbalanced”.


      1
      function isBalanced(root) {
    

      2
      function dfs(node) {
    

      3
        // Base case: empty subtree is balanced with height -1
    

      4
        if (node === null) return -1;
    

      5
        
    

      6
        // Recurse on left subtree
    

      7
        const leftHeight = dfs(node.left);
    

      8
        // If left is unbalanced, propagate the -1 sentinel
    

      9
        if (leftHeight === -1) return -1;
    

      10
        
    

      11
        // Recurse on right subtree
    

      12
        const rightHeight = dfs(node.right);
    

      13
        // If right is unbalanced, propagate the -1 sentinel
    

      14
        if (rightHeight === -1) return -1;
    

      15
        
    

      16
        // Check if this node is balanced
    

      17
        if (Math.abs(leftHeight - rightHeight) > 1) {
    

      18
          return -1; // Not balanced
    

      19
        }
    

      20
        
    

      21
        // Return the height of this subtree
    

      22
        return 1 + Math.max(leftHeight, rightHeight);
    

      23
      }
    

      24
       
    

      25
      return dfs(root) !== -1; // true if height was computed, false if -1 (unbalanced)
    

      26
      }

L1 Function checks if the tree is height-balanced and returns true/false.
L3 Base case: empty tree is balanced with height -1.
L6 Recurse left; get height (or -1 if unbalanced).
L8 Sentinel check: if left subtree is unbalanced, propagate the -1 up.
L11 Recurse right; get height (or -1 if unbalanced).
L13 Sentinel check: if right subtree is unbalanced, propagate the -1 up.
L16 If the absolute difference of heights is more than 1, this node is unbalanced.
L17 Return -1 (the sentinel) to propagate the unbalanced state up.
L21 Return the height of this subtree (the final answer for the parent).
L24 If dfs(root) is not -1, the tree is balanced.

Example: For the tree:

Node 4 (leaf): height = 0, balanced.
Node 3 (leaf): height = 0, balanced.
Node 2 (left child 4, no right): height = 0, left height = 0, right height = -1. Difference = |0 - (-1)| = 1 ≤ 1, balanced. Returns height 1.
Node 1 (left child 2, right child 3): height of left = 1, height of right = 0. Difference = |1 - 0| = 1 ≤ 1, balanced. Returns height 2.

Result: isBalanced(root) = true.

Running both on concrete trees

class Node {
constructor(value, left = null, right = null) {
  this.value = value;
  this.left = left;
  this.right = right;
}
}

// Diameter function
function diameterOfBinaryTree(root) {
let maxDiameter = 0;

function dfs(node) {
  if (node === null) return -1;
  const leftHeight = dfs(node.left);
  const rightHeight = dfs(node.right);
  const diameterThroughNode = leftHeight + rightHeight + 2;
  maxDiameter = Math.max(maxDiameter, diameterThroughNode);
  return 1 + Math.max(leftHeight, rightHeight);
}

dfs(root);
return maxDiameter;
}

// Height-balanced function
function isBalanced(root) {
function dfs(node) {
  if (node === null) return -1;
  const leftHeight = dfs(node.left);
  if (leftHeight === -1) return -1;
  const rightHeight = dfs(node.right);
  if (rightHeight === -1) return -1;
  if (Math.abs(leftHeight - rightHeight) > 1) return -1;
  return 1 + Math.max(leftHeight, rightHeight);
}
return dfs(root) !== -1;
}

// Build tree:
//      1
//     / \
//    2   3
//   / \
//  4   5

let node4 = new Node(4);
let node5 = new Node(5);
let node2 = new Node(2, node4, node5);
let node3 = new Node(3);
let root = new Node(1, node2, node3);

console.log("Diameter:", diameterOfBinaryTree(root));
console.log("Is balanced:", isBalanced(root));

Output

Step-by-step trace


      1
      let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    

      2
      diameterOfBinaryTree(root);

Complexity

Time complexity

The tree DP algorithms visit each node exactly once. At each node, we perform O(1) work (comparisons, arithmetic, variable updates). Since there are n nodes, the total time is O(n).

Space complexity

Both algorithms use recursion, so the call stack depth equals the height of the tree. In the worst case (a degenerate tree), height is O(n). In a balanced tree, height is O(log n).

Thus, space complexity is O(h), where h is the tree’s height.

Practice 0 / 5

In the tree DP pattern, what does a node return to its parent?

For a tree with this structure, what is the diameter (in edges)? ``` 1 / 2 / 3 ```

Why is a sentinel value (like -1) useful in the height-balanced tree check?

In the diameter algorithm, why is the base case return value -1 (not 0)?

Which of these is NOT a tree DP problem (where return value ≠ final answer)?

lesson.inset.undefined

Why tree DP matters. Many hard tree problems require computing two things at once: local information (height, count) that flows up, and global information (diameter, longest path) that is tracked on the side. Without tree DP, you might traverse the tree twice—once for heights, once for the diameter. Tree DP solves both in a single pass. This is why tree DP is an essential tool for interview problems and competitive programming.

lesson.inset.undefined

Confusing return value with the answer. Beginners often think the return value IS the final answer. But in tree DP, the return value is the local information (height), and the final answer is in a side variable (diameter). The return value is what the parent needs; the side variable is what you came to find. Keep them separate.

lesson.inset.undefined

Edge case: single-node tree. If the tree is just one node, the diameter is 0 (the longest path is the node itself, zero edges). With our height convention (null = -1, leaf = 0), the diameter calculation gives 0 + 0 + 2 = 2, which is wrong! The fix: account for this by starting maxDiameter at 0 and ensuring the diameter calculation correctly captures a single node. Our code does: a single node’s diameter = (-1) + (-1) + 2 = 0, but wait—that is wrong. Let me recalculate: a node with no children has leftHeight = rightHeight = -1. Diameter through it = -1 + (-1) + 2 = 0. This is correct! A single node has a diameter of 0 edges (the path is just itself).

Check yourself

Quiz

Explain the tree DP pattern: what is the return value vs. the side variable, and why does this pattern solve hard tree problems in a single pass?

Recap

Tree dynamic programming combines recursion with a side variable to solve tree problems in a single pass. The pattern: each node returns local information (like height) to its parent, while updating a side variable with the global answer (like diameter). The classic example is the diameter of a binary tree—the longest path between any two nodes. A height-balanced tree checker uses a sentinel value (-1) to encode both height and balance status in a single return. Tree DP is essential for hard tree problems: it avoids multiple passes and reveals the elegant, two-part structure of the solution. Next: Unit 08 covers heaps and priority queues, a different way to organize data for fast access to the minimum (or maximum) element.

Continue the climb ↑Trees: multiple-choice review