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.
- 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.
- 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
maxDepthat 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:
- Record:
l + ris the longest path that bends here, sobest = max(best, l + r). - 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:
- the number of generations (maximum depth),
- the two most distant relatives and how many steps apart they are (diameter, plus the two end nodes),
- 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
- 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.
- 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).
- 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.
- 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
- Does the diameter always pass through the root? No. Tree
uabove has diameter 4 through node 2, while the best path through the root is 3. - Why is the brute force O(n²) on a skewed tree?
maxDepthat each node walks its whole subtree; on a chain the subtree sizes are n, n-1, ..., 1, which add up to about n²/2. - 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 + rin a running maximum. - Time and space? O(n) time; O(h) space for the recursion (O(log n) balanced, O(n) skewed).
- What changes if the tree is 10⁶ levels deep? Recursion throws
StackOverflowErrorin Java (RecursionErrorin Python); use an iterative postorder with an explicit stack, or BFS for the depth. - 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.
- Why avoid a static field for
best? It keeps its value between calls; if you use one, reset it. Cleaner: anint[] bestparameter, 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), withnull→ 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 recordsbest = max(best, l + r): O(n), 14 ms on the big tree. - Watch out for: checking only the root,
+ 1(nodes vs edges), a staticbestnot reset, and very deep recursion.
Next episode: Lowest common ancestor: the closest ancestor two nodes share, the "bend" of the path between them.