Lesson 16.4 · Binary Trees

Returning Values Up the Tree

Each call returns one thing to its parent (like height), while a separate variable records the best answer seen anywhere (like the diameter).

14 min

Think of it like this

A company survey where every manager reports their team's headcount upwards, but separately tells HR if their own team is the largest seen. The number passed up and the number recorded aren't the same.

1.Two different quantities

For the diameter (longest path between any two nodes), a path through a node uses its left height plus its right height. But the parent can only extend one side of it. So the function returns the height (what the parent needs) and updates a global best with left + right (the answer through this node).

The same split appears in maximum path sum, longest univalue path and checking balance (return height or −1 for unbalanced).

Diameter.java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    TreeNode(int val) { this(val, null, null); }
}

public class Main {
    static int best = 0;
    static int height(TreeNode n) {               // returns height in nodes
        if (n == null) return 0;
        int l = height(n.left), r = height(n.right);
        best = Math.max(best, l + r);              // path through n, counted in edges
        return 1 + Math.max(l, r);                 // the parent can extend only one side
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
        height(root);
        System.out.println("diameter = " + best);
    }
}

Output

diameter = 3

Remember

Return what the parent needs; record the answer separately.
Post-order: children's results first, then the node.
Heights in nodes vs edges: be consistent.

Common mistakes

Returning the diameter instead of the height to the parent.
Mixing node-count and edge-count conventions.

Command Palette

Returning Values Up the Tree

1.Two different quantities