PK

PKBytes

Explore tracks
Chapter 24: Tree Fundamentals and Traversal
24.05Intermediate / Advanced6 topics17 min6 interactive animations

Structural computations

Computing properties of a tree from its subtrees: node count, height, diameter, the balance check, leaf count and the maximum path sum.

Learning goals

  • Compute a property by combining the answers from both subtrees
  • Calculate the diameter and the maximum path sum with a global best
  • Check balance without recomputing heights repeatedly
  • Use a sentinel value to stop early

Prerequisites

Traversal methods

Most tree questions have the same shape: ask each child a question, combine their answers, and sometimes record a candidate for a global answer on the way. The skill is deciding what to return and what to record.

24.05.1

Count nodes

The size of a tree is one for the root plus the sizes of its two subtrees, with 0 for an empty tree. This is postorder: the children answer first, and the parent combines. The animation shows n= under every node, the size of its subtree; on the “Count nodes” preset the root shows 6, the total.

Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).
24.05.2

Height

Height is one more than the taller child's height, with -1 for an empty tree. The animation shows h= under every node: leaves have 0, and the root of the “Height” preset (“1 2 3 4 5 # 6”) has 2 because the longest root-to-leaf path has 2 edges.

If a problem defines the height of a tree in nodes (a leaf has height 1), return 0 for the empty tree and add 1 as before; only the base case moves.

Java
1static int height(TreeNode n) {
2    if (n == null) return -1;
3    return 1 + Math.max(height(n.left), height(n.right));
4}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).
24.05.3

Diameter

The **diameter** is the number of edges on the longest path between any two nodes. That path may not go through the root. For each node, the longest path that *bends* at it has length height(left) + height(right) + 2 (edges, with -1 for a missing child). The answer is the maximum of that over all nodes, kept in a global variable while the function returns heights.

In the “Diameter (bends below the root)” preset the tree “1 2 3 4 5 # # 6 # # 7” has height 3, but the longest path 6 → 4 → 2 → 5 → 7 bends at node 2 and has 4 edges; a solution that only looked at the root would report less. Each call does O(1) work beyond its children, so the cost is O(n).

Java
1static int best;
2static int diameter(TreeNode root) {
3    best = 0;
4    heightOf(root);
5    return best;
6}
7static int heightOf(TreeNode n) {
8    if (n == null) return -1;
9    int l = heightOf(n.left), r = heightOf(n.right);
10    best = Math.max(best, l + r + 2);                // the path that bends at n uses both subtrees
11    return 1 + Math.max(l, r);
12}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).
24.05.4

Balanced tree check

A tree is **height-balanced** when at every node the heights of its two subtrees differ by at most 1. The straightforward solution calls height at every node and costs O(n²) on a chain. The linear solution returns the height from each call, and a sentinel (-2 here) when an imbalance has been found, which propagates up and stops the work early.

“3 9 20 # # 15 7” is balanced. “1 2 # 3 # 4” (a left chain of three below the root) is not: at the root the left subtree has height 2 and the right is empty (height -1), a difference of 3. The animation marks the first unbalanced node it meets, in post-order.

Java
1static boolean isBalanced(TreeNode root) {
2    return balancedHeight(root) != -2;
3}
4static int balancedHeight(TreeNode n) {              // -2 means "unbalanced somewhere below"
5    if (n == null) return -1;
6    int l = balancedHeight(n.left);
7    if (l == -2) return -2;
8    int r = balancedHeight(n.right);
9    if (r == -2) return -2;
10    if (Math.abs(l - r) > 1) return -2;
11    return 1 + Math.max(l, r);
12}

Best

O(1)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).
24.05.5

Leaf count

A leaf has no children, so it contributes 1; every other node contributes the leaf counts of its subtrees. Be careful with the base case: a node with exactly one child is not a leaf, and returning 1 for it (or for null) is the common bug. The “Leaf count” preset of “1 2 3 4 5 # 6” has 3 leaves (4, 5 and 6).

Java
1static int leaves(TreeNode n) {
2    if (n == null) return 0;
3    if (n.left == null && n.right == null) return 1; // a real leaf
4    return leaves(n.left) + leaves(n.right);
5}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).
24.05.6

Sum and max path sum

The **sum** of all values is the same combine-the-children pattern. The **maximum path sum** is the diameter pattern with values instead of edge counts: a path can start and end at any nodes. For each node compute the **gain** it can pass up, value + max(0, best gain from left, best gain from right); a negative gain is dropped, since not extending the path is better. The candidate answer at the node is value + max(0, left gain) + max(0, right gain), a path bending there.

In the “Maximum path sum (negatives)” preset the tree is “-10 9 20 # # 15 7”. Node 20 passes up 20 + 15 = 35; at the root the candidate would be -10 + 9 + 35 = 34, but the best path is 15 → 20 → 7 with sum 42, which bends at node 20.

Java
1static int bestPath;
2static int maxPathSum(TreeNode root) {
3    bestPath = Integer.MIN_VALUE;
4    gain(root);
5    return bestPath;
6}
7static int gain(TreeNode n) {                        // best downward path sum starting at n
8    if (n == null) return 0;
9    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));   // drop negative gains
10    bestPath = Math.max(bestPath, n.val + l + r);    // the path that bends at n
11    return n.val + Math.max(l, r);
12}
13
14static int sum(TreeNode n) {
15    return n == null ? 0 : n.val + sum(n.left) + sum(n.right);
16}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Computing node count, height, leaves, diameter, balance and path sum bottom-up

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

1
2
4
5
3
Combining the children nowValue computedNew bestUnbalanced
Setup

Diameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.

Step 1 / 7
Java
1static int countNodes(TreeNode n) {
2    if (n == null) return 0;
3    return 1 + countNodes(n.left) + countNodes(n.right);
4}
5static int height(TreeNode n) {                  // edges on the longest downward path; an empty tree is -1
6    if (n == null) return -1;
7    return 1 + Math.max(height(n.left), height(n.right));
8}
9static int leaves(TreeNode n) {
10    if (n == null) return 0;
11    if (n.left == null && n.right == null) return 1;
12    return leaves(n.left) + leaves(n.right);
13}
14static int best;
15static int diameterHeight(TreeNode n) {          // fills best with the most edges on any path
16    if (n == null) return -1;
17    int l = diameterHeight(n.left), r = diameterHeight(n.right);
18    best = Math.max(best, l + r + 2);            // the path that bends at n uses both subtrees
19    return 1 + Math.max(l, r);
20}
21static int balancedHeight(TreeNode n) {          // -2 means "unbalanced somewhere below"
22    if (n == null) return -1;
23    int l = balancedHeight(n.left); if (l == -2) return -2;
24    int r = balancedHeight(n.right); if (r == -2) return -2;
25    if (Math.abs(l - r) > 1) return -2;
26    return 1 + Math.max(l, r);
27}
28static int bestPath;
29static int gain(TreeNode n) {                    // best downward path sum starting at n
30    if (n == null) return 0;
31    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
32    bestPath = Math.max(bestPath, n.val + l + r);   // the path that bends at n
33    return n.val + Math.max(l, r);
34}

Live state

quantity

Diameter

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L15quantity=DiameterDiameter: every value is computed from the children's values, so the work happens after both subtrees return (post-order). A number under a node is its computed value.
2L18quantity=Diameter best=0A path bending at 4 has -1 + -1 + 2 = 0 edges (heights -1 and -1). New best diameter.
3L18quantity=Diameter best=0A path bending at 5 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
4L18quantity=Diameter best=2A path bending at 2 has 0 + 0 + 2 = 2 edges (heights 0 and 0). New best diameter.
5L18quantity=Diameter best=2A path bending at 3 has -1 + -1 + 2 = 0 edges (heights -1 and -1).
6L18quantity=Diameter best=3A path bending at 1 has 1 + 0 + 2 = 3 edges (heights 1 and 0). New best diameter.
7L19result=3Diameter: 3 edges (the longest path between any two nodes).

Practice ladder

Now try it yourself

Easy

  • Maximum Depth of Binary Tree
  • Diameter of Binary Tree
  • Balanced Binary Tree

Medium

  • Count Univalue Subtrees
  • Binary Tree Maximum Path Sum

Advanced

  • Binary Tree Cameras
  • Longest Univalue Path

Key takeaways

  • Most structural questions are postorder: combine the answers of the two subtrees.
  • The diameter and the maximum path sum record a candidate that bends at each node, and return a one-sided value upward.
  • Return a sentinel to stop early in the balance check, keeping it O(n).
  • A node with one child is not a leaf.