Height, balance and diameter

Why it matters

Height tells you the worst-case cost of most tree operations. A tree of height 5 needs at most 5 steps to reach any node, while a skewed tree of 1,000 nodes needs 1,000 steps. Diameter and balance checks are classic interview problems, and they teach a technique you will use again and again: the function returns one value to its parent, and it updates a second value that holds the answer for the whole tree. Once you can do that, many problems that look hard become a single recursive walk.

The idea: a subtree answers for itself

The recursive template from the first lesson says that a function answers for a node by asking its children. For height, the question is simple. How tall is the subtree rooted at this node?

Think of a family where each person knows the height of their own family line. A parent can work out the answer from the answers of the children: take the tallest child line, and add one for the parent. The same logic holds for a tree. The height of a node is one more than the larger of its two children's heights. A missing child has height 0, and so does an empty tree.

Before you write code, fix the convention. This lesson counts height in nodes. An empty tree has height 0, and a single node has height 1. Later in the lesson we switch to edges when we talk about diameter, because the diameter problem asks for edges. The difference is one, so you must check which one a problem uses.

Here is the tree we will use for the first three programs. It is built from the level-order list 1 2 3 4 5 -1 6, which you have seen before:

        1
       / \
      2   3
     / \   \
    4   5   6

The height of this tree, counted in nodes, is 3. The longest path from the root down is 1, 2, 4, which has three nodes. The path 1, 3, 6 also has three nodes.

Height

The code for height is short. The base case returns 0 for an empty tree. The recursive case returns one more than the larger of the two child heights.

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

Note the max function. It comes from the <algorithm> header, so you must include that header. The next program prints the height of the whole tree and the height of the right subtree, so you can see that the function works on any node, not just the root.

Type 1 2 3 4 5 -1 6 into the Input box and click Run.

height of whole tree: 3
height of right subtree: 2

Trace the calls. height(1) calls height(2) first. That calls height(4), which has no children and returns 1. Then height(5) returns 1 as well. So height(2) returns 1 + max(1, 1), which is 2. Back in height(1), the right call height(3) makes one call to height(6), which returns 1, and height(3) returns 1 + max(0, 1), which is 2. So height(1) returns 1 + max(2, 2), which is 3.

The output for the right subtree is 2, because the right child 3 has the chain 3, 6 below it, and that chain has two nodes.

The program has a bug that would bite you on a real test: when root is nullptr, the line root->right would crash. In this example the input is not empty, so it is safe. Lesson 1 taught the rule: check for null before you dereference, and this program trusts that the input has a root.

Time is O(n), because every node is visited once. Space is O(h), for the recursion depth.

The visualizer above shows frames for a recursive call as they go down and come back up. Watch how each frame waits for its children to return before it can compute its own answer. The height function behaves the same way: height(2) cannot finish until both height(4) and height(5) have returned.

Diameter: return one value, update another

The diameter of a tree is the number of edges on the longest path between any two nodes. The path does not have to go through the root. It can start at one leaf, climb to some node, and come down to another leaf in a different subtree.

Here is the key observation. Take any node. The longest path that bends at that node goes down its left side and down its right side. If the left subtree has height l in nodes, and the right has height r in nodes, the path has l nodes on the left and r nodes on the right, plus the node itself. Counted in edges, the bent path has l + r edges. For example, in the tree above, node 2 has a left height of 1 (node 4) and a right height of 1 (node 5), so the path 4, 2, 5 has 2 edges, which is 1 + 1.

So you want the largest l + r over all nodes. A slow approach would call height at each node, which walks the subtree again and again. On a skewed tree of n nodes, that adds up to about n squared work. The fast approach computes the heights and the best bent path in the same walk. That is the "return one value, update another" trick. The function returns the height, which its parent needs, and it updates a variable best, which only the top-level code needs.

int best = 0;
 
int heightAndDiameter(TreeNode* n) {
    if (!n) return 0;
    int l = heightAndDiameter(n->left);
    int r = heightAndDiameter(n->right);
    best = max(best, l + r);          // the path bending at n, in edges
    return 1 + max(l, r);             // the height of n, in nodes
}

Notice that best is a global variable here, which is a variable declared outside any function. That is simple, and it is acceptable for a short program. The next section shows a cleaner way to avoid globals.

Type 1 2 3 4 5 -1 6 into the Input box and click Run.

diameter in edges: 4

Here is the trace. Each row is one node. The left and right columns are the heights the node received from its children. The "best" column is the value of the global variable after the node finishes.

The last row gives the answer, 4. The path that bends at node 1 goes 4, 2, 1, 3, 6, which has four edges. Its left side is 2, 4 (height 2) and its right side is 3, 6 (height 2). This path bends at the root. Other diameter paths bend lower down, which is why the answer must be checked at every node.

The example tree with the longest path, 4, 2, 1, 3, 6, highlighted. It has four edges

Notice a subtle point. The node 3 bends with a left height of 0 and a right height of 1, which gives a path of only one edge on that side. The longest path is still 4, and it comes from node 1. So the best value is not always found at the root, and it is not always found at the deepest node. The code finds it by checking every node.

Time is O(n), because each node is visited once. Space is O(h), for the recursion.

Balance: a single pass with a sentinel

A tree is height-balanced if, at every node, the heights of the left and right subtrees differ by at most 1. Balanced trees keep the height near log n, so searching and inserting stay fast. Checking balance naively is slow: you compute the height at each node and compare, which again walks the subtrees many times. The trick is to combine the two steps in one walk, and to use a special return value, -1, to mean "not balanced".

That works because a height is never negative. Any return value of -1 can therefore only mean the sentinel, and the sentinel travels up the tree. As soon as a child returns -1, the parent returns -1 at once, so the walk stops early.

int check(TreeNode* n) {                // the height, or -1 if unbalanced
    if (!n) return 0;
    int l = check(n->left);
    if (l == -1) return -1;
    int r = check(n->right);
    if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}

The abs function returns the absolute value of an integer. It comes from <cstdlib>. Now type the two inputs below, one at a time, and compare the answers. The program prints balanced or not balanced. The first input is the tree from earlier, and the second is a tree that leans far to the left.

1 2 3 4 5 -1 6

1 2 3 4 -1 -1 -1 5

balanced

The output for the first input is balanced. For the second input, 1 2 3 4 -1 -1 -1 5, the program prints not balanced. The second tree is 1 with children 2 and 3, where 2 has a left child 4, and 4 has a left child 5. At node 1, the left height is 3 and the right height is 1, a difference of 2, so the tree is not balanced.

The trace for the second tree shows the early exit. check(5) returns 1. check(4) has a left height of 1 and a right height of 0, which is fine, so it returns 2. check(2) has a left height of 2 and a right height of 0, a difference of 2, so it returns -1. Then check(1) gets -1 from its left child, and returns -1 at once without even asking for the right child. The program then prints not balanced.

Time is O(n) in the worst case, and O(n) for the check that finds nothing wrong. Each node is visited once, and every call returns in constant time. Space is O(h).

Minimum depth: the shortest path to a leaf

The minimum depth asks for the number of nodes on the shortest path from the root down to any leaf. It is not the same as the height. The height follows the longest path, while the minimum depth stops at the nearest leaf.

Here is the classic mistake. A learner writes 1 + min(minDepth(left), minDepth(right)). That looks right, but a node with only one child has a missing side, and a missing side has depth 0. The min then picks 0, which is wrong, because a missing child is not a leaf. The fix is to handle the one-child case first: when one side is missing, the answer is the other side's depth plus one.

int minDepth(TreeNode* n) {
    if (!n) return 0;
    if (!n->left) return 1 + minDepth(n->right);
    if (!n->right) return 1 + minDepth(n->left);
    return 1 + min(minDepth(n->left), minDepth(n->right));
}

Test it on the input 1 2. The root 1 has a left child 2 and no right child. The shortest path to a leaf is 1, 2, which has two nodes. A wrong version that uses min naively would return 1, which is incorrect. The code above returns 2, because the first two checks handle the missing side.

Type 1 2 3 4 5 -1 6 into the Input box to see the minimum depth of the tree from the picture.

minimum depth: 3

The shortest paths are 1, 2, 4 and 1, 3, 6. Both have three nodes, so the answer is 3. The height of the same tree is also 3, because the longest path is the same length here. Change the input to 1 2 and the answer becomes 2, while the height is also 2. The two values only differ for trees that are lopsided, such as the tree 1 2 3 -1 -1 -1 4, where the nearest leaf is 2 but the deepest leaf is 4. Draw it in your head: the minimum depth is 2 nodes, and the height is 3 nodes.

Same tree: comparing two trees

A common interview question asks whether two trees are identical. Two trees are the same when they have the same shape and the same values at every position. The recursion is simple: two null trees are the same, a null tree and a real node are different, and two real nodes are the same when their values match and their left and right subtrees are the same.

bool same(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;        // both null: same; one null: different
    return a->val == b->val && same(a->left, b->left) && same(a->right, b->right);
}

The expression a == b gives true only when both pointers are null, because the first check handles the case where at least one is null. The && operator stops early: if the values differ, the recursive calls are never made. This is a short-circuit, and it saves work.

The program below reads two lines. Each line is one tree in the level-order format, so you need getline instead of reading numbers until the end. Type these two lines in the Input box, one line per tree:

1 2 3 4 5 -1 6
1 2 3 4 5 -1 5

different

The two trees differ only at the last position. The first tree has 6 as the right child of 3, and the second has 5 there. The comparison walks the trees together, finds the values differ at that node, and reports different. If you change the second line to match the first, the output becomes same.

Time is O(min(n1, n2)), because the walk stops at the first difference or at the end of the smaller tree. In the worst case, it visits every node of both trees.

A tip: keep state out of globals

The diameter code uses a global variable, best. Globals are easy to write, but they cause bugs when a test runs twice in the same program, because the old value stays. A cleaner way passes a reference to a variable from main, or wraps the state in a helper that is created fresh for each test. The C++ syntax for a reference parameter is int& best, which means the function changes the caller's variable. The function below does the same job without any global.

int heightDiameter(TreeNode* n, int& best) {
    if (!n) return 0;
    int l = heightDiameter(n->left, best);
    int r = heightDiameter(n->right, best);
    best = max(best, l + r);
    return 1 + max(l, r);
}

In main, you create int best = 0; and call heightDiameter(root, best). Each test then has its own best. Use this style in interview answers, because it shows that you think about state. The rest of the module uses globals only where they keep the code short.

Worked example: a skewed tree against a balanced tree

The shape of a tree decides how expensive its height is, so compare two trees with the same seven values. The first is a chain that leans right: 1 -1 2 -1 3 -1 4 -1 5 -1 6 -1 7. Every node has at most one child, and each child is on the right. The second is the perfect tree 1 2 3 4 5 6 7, which has three full levels.

Here is what the programs from this lesson print for each tree, in order: the height of the whole tree, the height of the right subtree, the diameter, the balance answer and the minimum depth.

For the chain, the output is:

height of whole tree: 7
height of right subtree: 6
diameter in edges: 6
not balanced
minimum depth: 7

For the perfect tree, the output is:

height of whole tree: 3
height of right subtree: 2
diameter in edges: 4
balanced
minimum depth: 3

Read the chain's output with care. The height is 7, because the chain has seven nodes in a row. The diameter is 6 edges, which is the path from node 1 down to node 7. The tree is not balanced, because node 5 has an empty left side and a right side of height 2, a difference of 2. The minimum depth is also 7, because a chain has only one leaf, and that leaf is the bottom of the chain.

The perfect tree tells the opposite story. Its height is 3, and its minimum depth is also 3, because every leaf is at the same depth. Its diameter is 4 edges, for the path 4, 2, 1, 3, 6. Its balance check passes at every node.

The difference shows up in cost. The height walk on the chain makes seven nested calls, and the call stack holds seven frames at its deepest point. On the perfect tree, the deepest point holds three frames. The total number of calls is the same, because every node is visited once, so the time is O(n) for both. The space for the call stack is O(h), so it is seven frames for the chain and three for the perfect tree. With a million nodes, the difference is between a million frames and about twenty, and the million-frame version can overflow the stack. That is why engineers care about height, and not only about the number of nodes.

What the call stack holds during the height walk

When height(1) runs, it calls height(2), and height(2) calls height(4). Until the call on 4 returns, the frames for 1 and 2 are still on the call stack, each waiting for its second child. This is the same stack of plates you saw in the traversal lesson, with one frame per node on the current path.

The deepest moment is the moment the walk reaches the bottom of the longest path. At that point the stack holds one frame for each node on that path, and that count equals the height. Once a leaf returns, its frame is removed, the parent looks at its other child, and the stack grows and shrinks again along other paths. The biggest the stack ever gets is the height of the tree, plus one for the call on the root.

This picture also explains the balance check's early exit. When the check finds a -1 at a node, it returns at once, so the frames for the nodes below that point are already gone, and the frames above it unwind one by one, each returning -1 as soon as it sees it. The walk stops, and the stack does not keep going down the rest of the tree.

Why the -1 sentinel is safe

The sentinel needs a value that no real height can take. Heights are counts of nodes, so they are 0 or more. The value -1 can never be a real height. That makes it a safe signal, because a parent that reads -1 knows for certain that something below it is unbalanced, and it does not have to compare the number with anything.

The sentinel also carries information up the tree. A real height tells the parent how tall the subtree is. A -1 tells the parent that the subtree is broken, and the parent passes the -1 up. Only one integer comes back from each call, but that integer carries two facts: the height when the subtree is fine, and the failure when it is not. This is the same "return one value, with a special meaning for one case" idea that the lowest common ancestor uses with null.

A bool version would need a second value to pass the height up, and that is awkward in recursion. The sentinel avoids the second value.

Edge cases in depth

Every function in this lesson should be tested on these inputs. Each one breaks a different kind of mistake.

• The empty tree, written -1. The height is 0, the diameter is 0, the balance check says balanced, and the minimum depth is 0. The minimum depth code returns 0 at its first line. A common mistake is to write the function so that it reads root->left before checking root, which crashes.
• One node, written 5. The height is 1, the diameter is 0 (there are no edges), the tree is balanced, and the minimum depth is 1. The node is a leaf, so the minimum depth stops at it.
• A chain that leans one way. The height is n, the minimum depth is n, and the balance check fails once a node has two or more nodes below it on one side and nothing on the other.
• Two children with one missing. Test 1 2 by hand. The minimum depth is 2, and the naive min version gives 1. This is the one-child trap from the minimum depth section.
• A tree where the diameter does not touch the root. Use 1 2 -1 3 4 5 -1 -1 6. The longest path is 4 edges, and the path through the root is only 3 edges.

Variations you will meet

The same walk answers many related questions. The change is always in what you do with the two child answers.

• Diameter through a given node. Take the height of the left subtree plus the height of the right subtree at that node, and nothing else. The total is the longest path that bends at that node. The interview version of this asks for the diameter of a specific subtree, and you only need the single-node formula.
• Maximum path sum from the root down to a leaf. Return the node's value plus the larger of the two child answers. Handle a missing child as a special case, as the minimum depth did, because a null child would otherwise add a fake 0 to the comparison.
• Count of nodes whose subtrees are balanced. Pass a counter by reference, and increase it at each node whose two child heights differ by at most 1. This needs the heights, so the walk is again postorder-style: the children answer first.
• Height in edges. Start from the height in nodes and subtract 1, except for the empty tree. Some problems return -1 for the empty tree, so the formula is heightEdges(n) = heightNodes(n) - 1 for a nonempty tree.

How to explain this in an interview

Interviewers want to hear your reasoning, so practise a short script. First, state the convention: "I'll count height in nodes, so an empty tree is 0." Second, state the base case and why it is safe. Third, say what each recursive call returns, in one sentence, such as "the height of the subtree rooted here." Fourth, say what you do with the two answers. Fifth, state the cost: one visit per node gives O(n) time, and the recursion depth gives O(h) space.

If the interviewer asks for the faster version, say that the naive balance check calls height at every node, and that the single pass avoids the repeated walks. Name the saving: on a skewed tree of n nodes, the naive check does about n squared steps, and the single pass does n.

Common mistakes and their real messages

Mixing node and edge counts

The most common error in this lesson is an off-by-one bug. If a problem asks for the diameter in edges, and your code returns 5 for the tree above when the answer is 4, the cause is usually that you added one for the node itself. Check the convention: the diameter formula l + r uses heights in nodes, so it gives edges, but a version that returns 1 + l + r would count nodes. Write down a tree with two nodes, with known answers, and test both your height and diameter on it before you trust either.

Recomputing height inside the balance check

A learner often writes if (abs(height(n->left) - height(n->right)) > 1) at every node. That is correct but slow, because height walks the whole subtree each time. On a skewed tree of 10,000 nodes, the total work is about 50 million steps. The single-pass version does 10,000. Always ask whether a helper function walks the same nodes again.

Forgetting the headers

The code in this lesson uses max and abs. If you leave out the headers, the compiler reports:

error: 'max' was not declared in this scope

With using namespace std, g++ may suggest the header to include. The fix is #include <algorithm> for max and min, and #include <cstdlib> for abs.

Forgetting to reset a global

If you run the diameter code twice in one program without resetting best, the second answer includes the first answer's maximum. That bug is silent: the output is a number, and it looks plausible. Set best = 0 before each test, or pass the variable as a reference, as shown above.

Assuming the diameter passes through the root

It is tempting to think that the diameter always bends at the root, so you could compute height(left) + height(right) at the root only. That is wrong. The tree 1 2 -1 3 4 5 -1 -1 6 has its longest path, 5, 3, 2, 4, 6, inside the left subtree of the root. That path has 4 edges. The path through the root has only 3 edges, from 5 up to 1. The only correct approach is to check every node, which is what the single-pass code does.

Debugging walkthrough

Suppose your diameter function returns 3 for the example tree, but the correct answer is 4. Follow these steps.

First, draw the tree and write the path you think is longest. For the example, the candidate path is 4, 2, 1, 3, 6, which you can count by hand. It has four edges. Your function reports 3, so it is missing a path, or it is adding wrong heights.

Second, print the heights at each node. Add a line cout << "node " << n->val << " l=" << l << " r=" << r << "\n"; before the return. Compare each printed pair with the trace table earlier in this lesson. The first row that differs is the place to look.

Third, check the return value. If heightAndDiameter returns l + r + 1 instead of 1 + max(l, r), the heights are wrong, and the mistake spreads upward. A node's height must be one more than the larger child, not the sum.

Fourth, test the smallest tree that breaks the code. A tree with 3 nodes, root 1 and children 2 and 3, has diameter 2, because the path 2, 1, 3 has two edges. If your function says 1 or 3, you have the convention wrong.

Interview questions you should be ready for

• How do you compute the height of a tree in one pass? Return one plus the larger child height, with an empty tree giving 0. This is O(n) time and O(h) space.
• How do you compute the diameter in one pass? Return the height from each node, and update a best value with left height plus right height at each node. Explain why the path can bend at any node, not only the root.
• How do you check whether a tree is balanced without repeated work? Return the height, or -1 as a sentinel for unbalanced, and stop as soon as a child returns -1.
• Why is the minimum depth not the same as the height? The height follows the deepest path. The minimum depth stops at the nearest leaf, and a missing child is not a leaf.
• What is the worst case for the naive balance check? A skewed tree, where computing the height at every node walks the whole chain each time, giving about n squared steps.

Real-world uses

A balanced tree keeps lookups fast, which is why databases and standard libraries use balanced trees for sorted data. The balance check is what a library runs after an insert to see whether a rotation is needed. Diameter-like questions appear in network design: the longest path in a tree of routers tells you the worst-case number of hops for a message. Minimum depth answers "how many steps until I reach something I can stop at," such as the closest folder with a given property in a file system.

Height matters most where reads are expensive. A database stores its index as a balanced tree with many children per node, so the height stays at three or four levels even for millions of rows. A lookup then reads only that many pages from disk, instead of walking a skewed tree that might read thousands. The balance rule in this lesson follows the same reasoning: you spend a little work on each insert to keep the height small for every later lookup.

Practice

1. Predict the height in nodes of the tree with input 1 2 -1 3. Then check it by running height on it.

2. Write int heightEdges(TreeNode* n) that returns the height in edges. An empty tree should return -1, so that a single node returns 0.

int heightEdges(TreeNode* n) {
    if (!n) return -1;
    return 1 + max(heightEdges(n->left), heightEdges(n->right));
}

3. Write bool isMirror(TreeNode* a, TreeNode* b) that returns true when the two trees are mirror images: the left of one matches the right of the other. Then write bool isSymmetric(TreeNode* root) that calls it on the root's two children.

bool isMirror(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;
    return a->val == b->val && isMirror(a->left, b->right) && isMirror(a->right, b->left);
}
 
bool isSymmetric(TreeNode* root) {
    return !root || isMirror(root->left, root->right);
}

4. Compute the sum of the depths of all leaves. Use depth 0 at the root. For the example tree, the leaves 4, 5 and 6 have depths 2, 2 and 2, so the answer is 6.

int sumLeafDepths(TreeNode* n, int depth) {
    if (!n) return 0;
    if (!n->left && !n->right) return depth;
    return sumLeafDepths(n->left, depth + 1) + sumLeafDepths(n->right, depth + 1);
}

5. Find the minimum depth without recursion, using level order. Hint: the first leaf you meet in a level-order walk is at the minimum depth.

int minDepthIter(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 1});
    while (!q.empty()) {
        auto [n, d] = q.front();
        q.pop();
        if (!n->left && !n->right) return d;
        if (n->left) q.push({n->left, d + 1});
        if (n->right) q.push({n->right, d + 1});
    }
    return 0;
}

6. Explain why the balance check that returns -1 can stop early, and why an ordinary bool version cannot.

7. Predict the diameter in edges of a perfect tree with four levels (depths 0 to 3). Show your reasoning with the bent path.

8. The naive minimum depth code 1 + min(minDepth(n->left), minDepth(n->right)) gives the wrong answer on the input 1 2. Explain why, and say what it returns.

9. Write int countBalancedNodes(TreeNode* n, int& count) that adds 1 to count for every node whose left and right heights differ by at most 1, and returns the height of n.

int countBalancedNodes(TreeNode* n, int& count) {
    if (!n) return 0;
    int l = countBalancedNodes(n->left, count);
    int r = countBalancedNodes(n->right, count);
    if (abs(l - r) <= 1) count++;
    return 1 + max(l, r);
}

10. Two-step question. A tree has height 4 (in nodes). What is the smallest number of nodes it can have, and what is the largest? Explain each case.

What you now know

• Height in nodes is one plus the larger child height, with an empty tree at 0. Check the convention before you write the code.
• The diameter is the largest left-height plus right-height over all nodes, in edges. The one-pass trick returns the height and updates a best value.
• The balance check uses -1 as a sentinel, so it stops early and visits each node once.
• Minimum depth follows the nearest leaf, and a node with one child must be handled as a special case.
• Two trees are the same when their values and shapes match at every position, and the walk stops at the first difference.
• Avoid repeated work, globals that leak between tests, and off-by-one errors in the node or edge convention.