SyntaxPilot
Courses/DSA and Coding Problems/Lesson 37
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 37 of 90

Maximum depth and diameter of a binary tree

queued

These are the notes for DSA episode 37. Last episode we built trees and walked them in four orders. Now we use that walk to measure a tree: its maximum depth (LeetCode 104) and its diameter (LeetCode 543). Maximum depth is a short postorder recursion. The diameter has a trap: the obvious solution calls maxDepth again at every node, which is O(n · h). It takes about 45 seconds on a big tree and gets Time Limit Exceeded. The fix is one postorder walk that returns a height and records the best path on the side, in O(n). Every program below was run with javac 21 (8-second time limit, like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

Picture a big family tree. The great-grandfather is at the top, his children below him, their children below them, and so on.

  1. How many generations does the family have? Start at the top, go down to the youngest person on any branch, and count the people on the way. That is the maximum depth.
  2. Which two relatives are the farthest apart? To get from one cousin to another you walk up to a shared grandparent and then down again. Count the parent-child steps. The largest count over all pairs is the diameter.

The twist: the two farthest relatives do not have to go through the great-grandfather. If one branch of the family is huge, both of them can be inside it.

In the family In the tree
The great-grandfather the root
One grandparent and all their descendants a subtree
A walk from one relative to another, via shared elders a path
Parent-child steps on that walk the path length (edges)
Number of generations the maximum depth (nodes on the longest root-to-leaf path)
The most distant pair of relatives the diameter (edges on the longest path)
The shared elder where the walk turns from up to down the bend (highest node) of the path

New words, from zero

  • Subtree of a node: that node plus everything below it. It is a tree of its own, with that node as its root.
  • Path: a sequence of nodes joined by edges, with no node used twice. A path may go up and then down.
  • Path length: the number of edges on the path (two nodes joined by one edge: length 1; a single node: length 0).
  • Maximum depth: the number of nodes on the longest path from the root down to a leaf. It equals the number of levels, the height from episode 36 (empty tree 0, one node 1).
  • Diameter: the number of edges on the longest path between any two nodes. It may or may not pass through the root.
  • Skewed tree (a chain): every node has at most one child. It is really a linked list, and the worst case for many tree algorithms, because its height is n.
  • Bend of a path (our word for it): the highest node on the path, where it stops going up and starts going down. Next episode gives it its proper name: the lowest common ancestor of the two end nodes.

Our two example trees:

tree t                         tree u
        1                              1
      /   \                           /
     2     3                         2
    / \     \                       / \
   4   5     6                     3   5
                                  /     \
                                 4       6
  • t: maximum depth 3 (1 → 2 → 4), diameter 4 (4 → 2 → 1 → 3 → 6), the path bends at the root.
  • u: maximum depth 4 (1 → 2 → 3 → 4), diameter 4 (4 → 3 → 2 → 5 → 6), the path bends at node 2 and never touches the root. Through the root, the best is only 3 edges (4 → 3 → 2 → 1).

Maximum depth (LeetCode 104)

Each node asks its two children "how many generations are below you?". An empty spot (null) answers 0. The node takes the bigger answer and adds one for itself:

maxDepth(null) = 0
maxDepth(n)    = 1 + max(maxDepth(n.left), maxDepth(n.right))

Both children answer before the parent, so this is a postorder traversal (left, right, node).

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int maxDepth(Node n) {
        if (n == null) return 0;
        int l = maxDepth(n.left);
        int r = maxDepth(n.right);
        return 1 + Math.max(l, r);
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        Node u = new Node(1, new Node(2, new Node(3, new Node(4), null),
                                     new Node(5, null, new Node(6))), null);
        System.out.println(maxDepth(t));
        System.out.println(maxDepth(null));
        System.out.println(maxDepth(new Node(7)));
        System.out.println(maxDepth(u));
    }
}

Real output:

3
0
1
4

Tree t: 3. Empty tree: 0. A single node: 1. Tree u: 4.

Maximum depth with BFS (no recursion)

Run the level-order BFS from episode 36 and count the levels:

    static int maxDepthBfs(Node root) {
        if (root == null) return 0;
        Deque<Node> q = new ArrayDeque<>();
        q.offer(root);
        int levels = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node n = q.poll();
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            levels++;
        }
        return levels;
    }

maxDepthBfs(t), maxDepthBfs(u), maxDepthBfs(null) print 3 4 0, and on a chain of 10 lakh nodes it prints 1000000, where the recursive version would throw StackOverflowError.

Problem statement: diameter of a binary tree

Diameter of Binary Tree (LeetCode 543). Given the root of a binary tree, return the length of the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

tree t                        →  4   (4 → 2 → 1 → 3 → 6)
tree u                        →  4   (4 → 3 → 2 → 5 → 6, the root is not on it)
empty tree (null)             →  0
one node                      →  0
chain 1 → 2 → 3               →  2

Brute force: try every node as the bend

Every path has one highest node, its bend. If a path bends at node n, it goes as deep as possible into the left subtree and as deep as possible into the right subtree. Going down from n to a node d levels below takes d edges, so the longest path bending at n has

maxDepth(n.left) + maxDepth(n.right)   edges

We don't know where the best bend is, so we try every node: the answer for a subtree is the best of (the path through this node, the best path inside the left subtree, the best path inside the right subtree).

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int maxDepth(Node n) {
        if (n == null) return 0;
        int l = maxDepth(n.left);
        int r = maxDepth(n.right);
        return 1 + Math.max(l, r);
    }
    static int bruteDiameter(Node n) {
        if (n == null) return 0;
        int through = maxDepth(n.left) + maxDepth(n.right);
        int inLeft = bruteDiameter(n.left);
        int inRight = bruteDiameter(n.right);
        return Math.max(through, Math.max(inLeft, inRight));
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        Node u = new Node(1, new Node(2, new Node(3, new Node(4), null),
                                     new Node(5, null, new Node(6))), null);
        System.out.println(bruteDiameter(t));
        System.out.println(bruteDiameter(u));
    }
}

Real output:

4
4

Correct for both trees, because node 2 of u gets its turn as the bend.

The big input

A chain of 5,000 nodes going left, with a complete tree 21 levels deep (2^21 - 1 = 20,97,151 nodes, about 20 lakh) hanging at the bottom:

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int maxDepth(Node n) {
        if (n == null) return 0;
        int l = maxDepth(n.left);
        int r = maxDepth(n.right);
        return 1 + Math.max(l, r);
    }
    static int bruteDiameter(Node n) {
        if (n == null) return 0;
        int through = maxDepth(n.left) + maxDepth(n.right);
        int inLeft = bruteDiameter(n.left);
        int inRight = bruteDiameter(n.right);
        return Math.max(through, Math.max(inLeft, inRight));
    }
    static Node full(int depth) {
        if (depth == 0) return null;
        return new Node(depth, full(depth - 1), full(depth - 1));
    }
    static Node bigTree() {
        Node root = new Node(0), cur = root;
        for (int i = 1; i < 5000; i++) {
            cur.left = new Node(i);
            cur = cur.left;
        }
        cur.left = full(21);
        return root;
    }
    public static void main(String[] args) {
        Node big = bigTree();
        long t0 = System.nanoTime();
        int d = bruteDiameter(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("diameter " + d + ", " + ms + " ms");
    }
}

Real result: Time Limit Exceeded in the SyntaxPilot compiler. Run locally without a limit, it printed diameter 5020, 44661 ms (about 45 seconds).

Why the brute force is slow

  • maxDepth at a node walks that node's whole subtree.
  • So every node is walked again once for each of its ancestors: by the root's call, by the root's child's call, and so on.
  • The 20 lakh nodes at the bottom each have about 5,000 ancestors: about 20,00,000 × 5,000 = 1,000 crore node visits.
  • In general the cost is the sum of all subtree sizes, which is O(n · h): about O(n log n) for a balanced tree and O(n²) for a skewed tree (a chain).

The waste: when maxDepth runs at a node, it already computes the left depth l and the right depth r, the exact two numbers the diameter needs, and then throws them away.

The key insight: one walk, two jobs

Let one postorder function, height(n), do both jobs at every node:

  1. Record: l + r is the longest path that bends here, so best = max(best, l + r).
  2. Return: 1 + max(l, r), the height, so the parent can do the same.

The function returns one thing (the height) and records another (the diameter) on the side. Every node is visited once: O(n).

Trace on tree t (children answer first; best starts at 0):

Node l r l + r best after returns
4 (leaf) 0 0 0 0 1
5 (leaf) 0 0 0 0 1
2 1 1 2 2 2
6 (leaf) 0 0 0 2 1
3 0 1 1 2 2
1 (root) 2 2 4 4 3

One walk gives both answers: the root returns 3 (the maximum depth) and best is 4 (the diameter).

The optimal solution in Java

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int height(Node n) {
        if (n == null) return 0;
        int l = height(n.left);
        int r = height(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        best = 0;
        height(root);
        return best;
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        Node u = new Node(1, new Node(2, new Node(3, new Node(4), null),
                                     new Node(5, null, new Node(6))), null);
        Node c = new Node(1, new Node(2, new Node(3), null), null);
        System.out.println(diameter(t));
        System.out.println(diameter(u));
        System.out.println(diameter(null));
        System.out.println(diameter(new Node(7)));
        System.out.println(diameter(c));
    }
}

Real output:

4
4
0
0
2

Tree t: 4. Tree u: 4 (bend at node 2). Empty tree: 0. One node: 0. Chain c (1 → 2 → 3): 2. All five correct.

The big tree:

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int height(Node n) {
        if (n == null) return 0;
        int l = height(n.left);
        int r = height(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        best = 0;
        height(root);
        return best;
    }
    static Node full(int depth) {
        if (depth == 0) return null;
        return new Node(depth, full(depth - 1), full(depth - 1));
    }
    static Node bigTree() {
        Node root = new Node(0), cur = root;
        for (int i = 1; i < 5000; i++) {
            cur.left = new Node(i);
            cur = cur.left;
        }
        cur.left = full(21);
        return root;
    }
    public static void main(String[] args) {
        Node big = bigTree();
        long t0 = System.nanoTime();
        int d = diameter(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("diameter " + d + ", " + ms + " ms");
    }
}

Real output: diameter 5020, 14 ms (14 ms in one run, against about 45 seconds for the brute force). 5020 = 5,000 edges down the chain plus 20 edges down the complete tree.

The same code in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

int maxDepth(Node* n) {
    if (!n) return 0;
    return 1 + max(maxDepth(n->left), maxDepth(n->right));
}

int bruteDiameter(Node* n) {                 // O(n · h)
    if (!n) return 0;
    int through = maxDepth(n->left) + maxDepth(n->right);
    return max(through, max(bruteDiameter(n->left), bruteDiameter(n->right)));
}

int height(Node* n, int& best) {             // one postorder walk
    if (!n) return 0;
    int l = height(n->left, best);
    int r = height(n->right, best);
    best = max(best, l + r);
    return 1 + max(l, r);
}

int diameter(Node* root) {
    int best = 0;
    height(root, best);
    return best;
}

int main() {
    Node* t = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, nullptr, new Node(6)));
    Node* u = new Node(1, new Node(2, new Node(3, new Node(4)), new Node(5, nullptr, new Node(6))));
    Node* c = new Node(1, new Node(2, new Node(3)));
    cout << "maxDepth: " << maxDepth(t) << ' ' << maxDepth(nullptr) << ' '
         << maxDepth(new Node(7)) << ' ' << maxDepth(u) << '\n';
    cout << "brute:    " << bruteDiameter(t) << ' ' << bruteDiameter(u) << '\n';
    cout << "diameter: " << diameter(t) << ' ' << diameter(u) << ' ' << diameter(nullptr) << ' '
         << diameter(new Node(7)) << ' ' << diameter(c) << '\n';
}

Real output (g++ -O2):

maxDepth: 3 0 1 4
brute:    4 4
diameter: 4 4 0 0 2

In C++ (and in Python below) best is passed by reference or captured, instead of being a static field, so there is nothing to reset between calls.

The same code in Python

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_depth(n):
    if n is None:
        return 0
    return 1 + max(max_depth(n.left), max_depth(n.right))

def max_depth_bfs(root):                     # count the levels, no recursion
    if root is None:
        return 0
    q, levels = deque([root]), 0
    while q:
        for _ in range(len(q)):
            n = q.popleft()
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        levels += 1
    return levels

def brute_diameter(n):                       # O(n · h)
    if n is None:
        return 0
    through = max_depth(n.left) + max_depth(n.right)
    return max(through, brute_diameter(n.left), brute_diameter(n.right))

def diameter(root):                          # one postorder walk, O(n)
    best = 0
    def height(n):
        nonlocal best
        if n is None:
            return 0
        l, r = height(n.left), height(n.right)
        best = max(best, l + r)
        return 1 + max(l, r)
    height(root)
    return best

t = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
u = Node(1, Node(2, Node(3, Node(4)), Node(5, None, Node(6))))
c = Node(1, Node(2, Node(3)))
print("max_depth:", max_depth(t), max_depth(None), max_depth(Node(7)), max_depth(u))
print("bfs:      ", max_depth_bfs(t), max_depth_bfs(None), max_depth_bfs(u))
print("brute:    ", brute_diameter(t), brute_diameter(u))
print("diameter: ", diameter(t), diameter(u), diameter(None), diameter(Node(7)), diameter(c))

Real output (python3):

max_depth: 3 0 1 4
bfs:       3 0 4
brute:     4 4
diameter:  4 4 0 0 2

Python's default recursion limit is 1000, so the recursive versions fail on a chain deeper than about 1000 nodes with RecursionError: maximum recursion depth exceeded; max_depth_bfs has no such limit.

Three real bugs

Bug 1: checking only the path through the root

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int maxDepth(Node n) {
        if (n == null) return 0;
        int l = maxDepth(n.left);
        int r = maxDepth(n.right);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        if (root == null) return 0;
        return maxDepth(root.left) + maxDepth(root.right);
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        Node u = new Node(1, new Node(2, new Node(3, new Node(4), null),
                                     new Node(5, null, new Node(6))), null);
        System.out.println(diameter(t));
        System.out.println(diameter(u));
    }
}

Real output:

4
3

t looks right by luck, but u gives 3 instead of 4: its longest path bends at node 2, and this code only ever looks at the root. Check l + r at every node.

Bug 2: counting nodes instead of edges

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int height(Node n) {
        if (n == null) return 0;
        int l = height(n.left);
        int r = height(n.right);
        best = Math.max(best, l + r + 1);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        best = 0;
        height(root);
        return best;
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        Node u = new Node(1, new Node(2, new Node(3, new Node(4), null),
                                     new Node(5, null, new Node(6))), null);
        System.out.println(diameter(t));
        System.out.println(diameter(u));
        System.out.println(diameter(new Node(7)));
    }
}

Real output:

5
5
1

Every answer is one too big. The path 4 → 2 → 1 → 3 → 6 has 5 nodes but 4 edges, and the diameter counts edges. (Maximum depth counts nodes; diameter counts edges.)

Bug 3: not resetting the static best

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int height(Node n) {
        if (n == null) return 0;
        int l = height(n.left);
        int r = height(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        height(root);
        return best;
    }
    public static void main(String[] args) {
        Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
                             new Node(3, null, new Node(6)));
        System.out.println(diameter(t));
        System.out.println(diameter(new Node(7)));
        System.out.println(diameter(null));
    }
}

Real output:

4
4
4

A single node and an empty tree should both be 0. best is a static field, so it still holds 4 from the first call. Judges like LeetCode call your function many times in one run, so this fails there too. Reset best = 0; at the start of diameter, or avoid the field (pass an int[] best or return a pair).

Also: StackOverflowError on a very deep chain

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
    }
    static int best;
    static int height(Node n) {
        if (n == null) return 0;
        int l = height(n.left);
        int r = height(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    static int diameter(Node root) {
        best = 0;
        height(root);
        return best;
    }
    static Node chain(int n) {
        Node root = new Node(0), cur = root;
        for (int i = 1; i < n; i++) {
            cur.left = new Node(i);
            cur = cur.left;
        }
        return root;
    }
    public static void main(String[] args) {
        System.out.println(diameter(chain(1000000)));
    }
}

Real output (the trace repeats for 1,024 lines):

Exception in thread "main" java.lang.StackOverflowError
    at Main.height(Main.java:12)
    at Main.height(Main.java:13)
    at Main.height(Main.java:13)
    ...

Each level of recursion needs a stack frame, and the default Java thread stack holds only some thousands of these. On my machine, a 5,000-deep tree was fine and a 10,000-deep one already overflowed (that is why the big input uses a 5,000-node chain). For trees that deep, use an iterative walk with your own stack (or BFS for the maximum depth).

Complexity

Algorithm Time Extra space
maxDepth, recursive O(n) O(h) recursion stack
maxDepth, BFS O(n) O(w) queue, w = widest level
Diameter, brute force (maxDepth at every node) O(n · h): O(n log n) balanced, O(n²) skewed O(h)
Diameter, one postorder walk O(n) O(h) recursion stack

h is about log n for a balanced tree and n for a chain. On the big tree: brute force about 45 s (TLE), one walk 14 ms.

Common mistakes

Mistake What you see Why Fix
Only maxDepth(root.left) + maxDepth(root.right) tree u: 3 (should be 4) the longest path can bend below the root check l + r at every node
best = Math.max(best, l + r + 1) 5, 5, 1 (one too big) counted nodes, not edges best = Math.max(best, l + r)
No best = 0; in diameter() single node: 4 (should be 0) the static field keeps the last answer reset at the start, or avoid the field
return l + r; instead of return 1 + Math.max(l, r); 0 for every tree mixed up what to record and what to return return the height, record the path
Recursion on a 10 lakh-node chain java.lang.StackOverflowError one stack frame per level iterative walk / BFS
Recursion on a deep chain in Python RecursionError: maximum recursion depth exceeded default limit 1000 BFS / explicit stack

Mini project: the family tree report

Build a family as a binary tree with names (Node with a String name). Print:

  1. the number of generations (maximum depth),
  2. the two most distant relatives and how many steps apart they are (diameter, plus the two end nodes),
  3. the person where that path bends.

Hint for 2 and 3: make height return the deepest node below each node along with the height (a small class with int h; Node deepest;). When l + r beats best, remember the deepest node on the left, the deepest node on the right, and the current node (the bend).

Practice

  1. Minimum depth (LeetCode 111): the number of nodes on the shortest root-to-leaf path.
Solution

Careful: a node with one child is not a leaf, so you can't just take min(left, right).

    static int minDepth(Node n) {
        if (n == null) return 0;
        if (n.left == null) return 1 + minDepth(n.right);
        if (n.right == null) return 1 + minDepth(n.left);
        return 1 + Math.min(minDepth(n.left), minDepth(n.right));
    }

minDepth(t) = 3, minDepth(u) = 4 (u's only leaves are 4 and 6). Real output: 3 4. BFS that stops at the first leaf is faster on wide trees.

  1. Balanced binary tree (LeetCode 110): at every node, the left and right heights differ by at most 1.
Solution

The same trick as the diameter: return the height, and report a problem on the side (here by returning -1).

    static int check(Node n) {
        if (n == null) return 0;
        int l = check(n.left);
        if (l == -1) return -1;
        int r = check(n.right);
        if (r == -1) return -1;
        if (Math.abs(l - r) > 1) return -1;
        return 1 + Math.max(l, r);
    }
    static boolean isBalanced(Node root) { return check(root) != -1; }

isBalanced(t) → true, isBalanced(u) → false (at the root, left height 3, right 0). O(n).

  1. Maximum depth without recursion.
Solution

maxDepthBfs above: BFS, add 1 per level. On a chain of 10 lakh nodes it prints 1000000 with no stack overflow.

  1. Diameter that also returns the path's length in nodes.
Solution

Nodes on a path = edges + 1, so return diameter(root) + 1 for a non-empty tree (and 0 for an empty one). This is what bug 2 accidentally computed.

Quick quiz

A chain of 5 nodes, 1 → 2 → 3 → 4 → 5. What are its maximum depth and diameter? (a) 5 and 5 (b) 5 and 4 (c) 4 and 4 (d) 4 and 5

Answer

(b) 5 and 4. Maximum depth counts nodes on the root-to-leaf path: 5. Diameter counts edges on the longest path: 5 nodes in a line have 4 edges between them.

Interview questions

  1. Does the diameter always pass through the root? No. Tree u above has diameter 4 through node 2, while the best path through the root is 3.
  2. Why is the brute force O(n²) on a skewed tree? maxDepth at each node walks its whole subtree; on a chain the subtree sizes are n, n-1, ..., 1, which add up to about n²/2.
  3. How does the optimal solution get both values in one walk? The postorder function returns the height to its parent and, at each node, records l + r in a running maximum.
  4. Time and space? O(n) time; O(h) space for the recursion (O(log n) balanced, O(n) skewed).
  5. What changes if the tree is 10⁶ levels deep? Recursion throws StackOverflowError in Java (RecursionError in Python); use an iterative postorder with an explicit stack, or BFS for the depth.
  6. Max depth counts nodes, diameter counts edges: why? These are the problems' definitions (LeetCode 104 and 543). Always check which one a problem uses; mixing them gives off-by-one answers.
  7. Why avoid a static field for best? It keeps its value between calls; if you use one, reset it. Cleaner: an int[] best parameter, or return a small object with both values.

Glossary

Term Meaning
Binary tree A tree where every node has at most two children, left and right (episode 36)
Node / edge / root / leaf An item / the link from a parent to a child / the top node / a node with no children
Subtree A node plus everything below it
Path A sequence of nodes joined by edges, no node repeated; it may go up then down
Path length The number of edges on a path
Height The number of levels of a (sub)tree: empty 0, one node 1
Maximum depth The number of nodes on the longest root-to-leaf path (= height)
Minimum depth The number of nodes on the shortest root-to-leaf path
Diameter The number of edges on the longest path between any two nodes
Bend (of a path) The highest node on a path, where it turns from going up to going down
Skewed tree / chain A tree where every node has at most one child; height n
Balanced tree A tree where, at every node, left and right heights differ by at most 1
Postorder Left, right, then the node: children answer before the parent
BFS Breadth-first search: one level at a time, with a queue
Brute force The straightforward solution that tries everything, often slow
O(n · h) Work proportional to the number of nodes times the height
Static field A variable that belongs to the class and keeps its value between calls
StackOverflowError Java's error when recursion goes too deep for the thread's stack
RecursionError Python's error when recursion passes the recursion limit (1000 by default)
Time Limit Exceeded (TLE) The judge stopped the program for running too long (8 s here)

Summary

  • Maximum depth = 1 + max(left, right), with null → 0: a postorder walk, O(n). BFS counting levels gives the same answer without recursion.
  • Diameter = the longest path in edges, and it can bend at any node, not only the root.
  • Brute force: maxDepth(left) + maxDepth(right) at every node: O(n · h), O(n²) on a chain, about 45 s (TLE) on the big tree.
  • Optimal: one postorder walk that returns 1 + max(l, r) and records best = max(best, l + r): O(n), 14 ms on the big tree.
  • Watch out for: checking only the root, + 1 (nodes vs edges), a static best not reset, and very deep recursion.

Next episode: Lowest common ancestor: the closest ancestor two nodes share, the "bend" of the path between them.