15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The height of a binary tree is the number of edges on the longest downward path from the root to a leaf. A leaf has height 0 and an empty tree has height -1. Compute it recursively as 1 + max(left height, right height) in O(n) time and O(h) stack space.
| Height of a leaf | 0, no downward edges |
|---|---|
| Height of an empty tree | -1, the base case for the recurrence |
| Height formula | 1 + max(height(left), height(right)) |
| Size formula | 1 + size(left) + size(right) |
| Time and space | O(n) time, O(h) recursion stack |
You should already be comfortable with these ideas:
left child and a right child. Either child may be null.Two measurements are used:
The height convention is:
height(null) = -10, because it has no downward edges.1.Use this tree for the whole lesson:
1 A
2 / \
3 B C
4 / \
5 D EA is the root. B and C are its children. D and E are children of B.
Start with the boundary underneath every leaf: a null child.
1height(null) = -1
2size(null) = 0Look at the path A → B → D.
1A -- B -- DThere are two edges from A to D, one edge from B to D, and zero edges from D to itself.
So:
1height(D) = 0
2height(B) = 1
3height(A) = 2For size, count each non-null node once:
1A, B, C, D, E → size(A) = 5A recursive call moves downward before it can compute a parent’s answer. The parent computes after both child calls return.
Null gives size 0, height -1. D and E give (1, 0), B gives (3, 1), C gives (1, 0), and A gives (5, 2).
Each call returns a summary of its complete subtree:
1(size, height)Follow the return values from the bottom of the example tree.
| State | Calls or returns | Returned size | Returned height |
|---|---|---|---|
| 0 | At every null child of D | 0 | -1 |
| 1 | D combines its two null-child results | 1 | 0 |
| 1 | E combines its two null-child results | 1 | 0 |
| 2 | B combines results from D and E | 1 + 1 + 1 = 3 | 1 + max(0, 0) = 1 |
| 3 | C has two null children | 1 | 0 |
| 4 | A combines results from B and C | 1 + 3 + 1 = 5 | 1 + max(1, 0) = 2 |
At B, size uses both child sizes because all nodes in both subtrees belong to B’s subtree.
1size(B) = 1 + size(D) + size(E)
2 = 1 + 1 + 1
3 = 3Height uses only the larger child height. A longest root-to-leaf path chooses one branch; it cannot travel down both branches.
1height(B) = 1 + max(height(D), height(E))
2 = 1 + max(0, 0)
3 = 1After a recursive call finishes, its returned values describe the complete subtree rooted at the node passed to that call.
More precisely:
When a recursive call for a node returns, its size result equals the number of nodes in that node’s subtree and its height result equals the longest downward edge count from that node to a leaf.
A parent can use the returned child values without visiting the child subtree again.
For example, when the call for B returns:
1size(B) = 3
2height(B) = 1A does not need to visit D and E again. The result from B already includes both nodes.
Start with the boundary case.
If the input subtree is empty:
1size(null) = 0
2height(null) = -1Perform this check before accessing left or right. A null reference has no child fields to read.
For a non-null node:
For size, count the current node once:
1size(node) = 1 + size(node.left) + size(node.right)For height, choose the taller child subtree, then add the one edge from the current node to that child:
1height(node) = 1 + max(height(node.left), height(node.right))The order is postorder-style: child results arrive before the parent computes its own result.
Check the required boundaries with concrete trees:
| Input | Size | Edge-based height |
|---|---|---|
| Empty tree | 0 | -1 |
Single node A | 1 | 0 |
Left chain A → B → C | 3 | 2 |
Root A with leaf children B and C | 3 | 1 |
| Root with a deep left subtree and a shallow right leaf | Counts all nodes | Follows the left subtree only when it is longer |
Node is a binary-tree node with these fields:
1node.left // a Node or null
2node.right // a Node or nullBoth functions accept the root of a subtree. They return one integer and do not mutate the tree.
11 function treeSize(root) -> integer
22 input: root, a Node or null
33 returns: number of non-null nodes in root's subtree
44 mutation: does not modify any node or child link
55
66 if root = null
77 return 0
88
99 leftSize <- treeSize(root.left)
1010 rightSize <- treeSize(root.right)
1111 return 1 + leftSize + rightSize112 function treeHeight(root) -> integer
213 input: root, a Node or null
314 returns: longest downward path from root to a leaf, measured in edges
415 mutation: does not modify any node or child link
516
617 if root = null
718 return -1
819
920 leftHeight <- treeHeight(root.left)
1021 rightHeight <- treeHeight(root.right)
1122 return 1 + max(leftHeight, rightHeight)The max(x, y) helper returns the larger of its two integer inputs.
Use the original tree:
1 A
2 / \
3 B C
4 / \
5 D EtreeSize(A)The calls go downward through lines 9 and 10. The values return through lines 7 and 11.
| Step | Active call and executed line | Result passed upward |
|---|---|---|
| 1 | treeSize(A), line 9 calls treeSize(B) | Waiting for leftSize |
| 2 | treeSize(B), line 9 calls treeSize(D) | Waiting for leftSize |
| 3 | treeSize(D), line 9 calls treeSize(null) | Waiting for leftSize |
| 4 | treeSize(null), line 6 is true; line 7 returns 0 | D.leftSize = 0 |
| 5 | treeSize(D), line 10 calls treeSize(null) | Waiting for rightSize |
| 6 | treeSize(null), line 6 is true; line 7 returns 0 | D.rightSize = 0 |
| 7 | treeSize(D), line 11 returns 1 + 0 + 0 | D returns 1 to B |
| 8 | treeSize(B), line 10 calls treeSize(E) | Waiting for rightSize |
| 9 | treeSize(E), line 9 calls treeSize(null) | Waiting for leftSize |
| 10 | treeSize(null), line 7 returns 0 | E.leftSize = 0 |
| 11 | treeSize(E), line 10 calls treeSize(null) | Waiting for rightSize |
| 12 | treeSize(null), line 7 returns 0 | E.rightSize = 0 |
| 13 | treeSize(E), line 11 returns 1 + 0 + 0 | E returns 1 to B |
| 14 | treeSize(B), line 11 returns 1 + 1 + 1 | B returns 3 to A |
| 15 | treeSize(A), line 10 calls treeSize(C) | Waiting for rightSize |
| 16 | treeSize(C), lines 9 and 10 each call treeSize(null) | Both calls return 0 from line 7 |
| 17 | treeSize(C), line 11 returns 1 + 0 + 0 | C returns 1 to A |
| 18 | treeSize(A), line 11 returns 1 + 3 + 1 | treeSize(A) returns 5 |
At step 16, treeSize(C) first calls treeSize(null) through line 9 and receives 0 for C.leftSize. It then calls treeSize(null) through line 10 and receives 0 for C.rightSize.
treeHeight(A)The calls follow the same left-child-then-right-child order. The base value is -1, and line 22 uses max instead of adding both child results.
| Step | Active call and executed line | Result passed upward |
|---|---|---|
| 1 | treeHeight(A), line 20 calls treeHeight(B) | Waiting for leftHeight |
| 2 | treeHeight(B), line 20 calls treeHeight(D) | Waiting for leftHeight |
| 3 | treeHeight(D), lines 20 and 21 call its null children | Each null call returns -1 from line 18 |
| 4 | treeHeight(D), line 22 returns 1 + max(-1, -1) | D returns 0 to B |
| 5 | treeHeight(B), line 21 calls treeHeight(E) | Waiting for rightHeight |
| 6 | treeHeight(E), lines 20 and 21 call its null children | Each null call returns -1 from line 18 |
| 7 | treeHeight(E), line 22 returns 1 + max(-1, -1) | E returns 0 to B |
| 8 | treeHeight(B), line 22 returns 1 + max(0, 0) | B returns 1 to A |
| 9 | treeHeight(A), line 21 calls treeHeight(C) | Waiting for rightHeight |
| 10 | treeHeight(C), lines 20 and 21 call its null children | Each null call returns -1 from line 18 |
| 11 | treeHeight(C), line 22 returns 1 + max(-1, -1) | C returns 0 to A |
| 12 | treeHeight(A), line 22 returns 1 + max(1, 0) | treeHeight(A) returns 2 |
At step 3, treeHeight(D) calls its left null child through line 20 and receives -1 for D.leftHeight. It then calls its right null child through line 21 and receives -1 for D.rightHeight.
At step 6, treeHeight(E) calls its left null child through line 20 and receives -1 for E.leftHeight. It then calls its right null child through line 21 and receives -1 for E.rightHeight.
At step 10, treeHeight(C) calls its left null child through line 20 and receives -1 for C.leftHeight. It then calls its right null child through line 21 and receives -1 for C.rightHeight.
The final results are:
1treeSize(A) = 5
2treeHeight(A) = 2Use a structural argument over binary-tree subtrees.
For treeSize(null), line 7 returns 0. An empty subtree contains zero non-null nodes.
For treeHeight(null), line 18 returns -1. The edge-based height convention defines the height of an empty subtree as -1.
The base cases are checked before reading root.left or root.right, so neither function accesses child fields of null.
Assume the calls for root.left and root.right return correct values for their complete subtrees.
For size:
leftSize is the number of nodes in the left subtree.rightSize is the number of nodes in the right subtree.root is one additional node.So line 11 returns exactly the number of nodes in the full subtree:
11 + leftSize + rightSizeFor height:
leftHeight is the longest downward edge count in the left subtree.rightHeight is the longest downward edge count in the right subtree.root continues into either the left or right subtree.max(leftHeight, rightHeight).root to the chosen child adds one edge.So line 22 returns the correct edge-based height:
11 + max(leftHeight, rightHeight)Every non-null recursive call moves to a child subtree. Child subtrees are smaller than the current subtree. Eventually a call receives null and returns immediately.
Both functions terminate, and each returned result satisfies the stated subtree property.
Let n be the number of non-null nodes.
For treeSize:
Constant work occurs at each of n nodes, so the running time is:
1O(n)For treeHeight:
max comparison and one addition.The running time is:
1O(n)Active calls form one root-to-leaf path. If the tree height is h edges, that path contains O(h) active non-null calls. Recursive auxiliary space is:
1O(h)Neither basic implementation creates an array, queue, or per-node cache. There is no additional O(n) auxiliary structure.
For the worked example, n = 5 and h = 2. The longest active non-null chain is A, B, D.
Incorrect line:
1return leftSize + rightSizeSmallest exposing input:
1ABoth child calls return 0, so the incorrect result is:
10 + 0 = 0But the tree contains node A, so its size is 1.
Correction:
1return 1 + leftSize + rightSizeIncorrect line:
1return 1 + leftHeight + rightHeightA root with two leaf children does not expose the error:
1 A
2 / \
3 B CIt incorrectly computes 1 + 0 + 0 = 1, which happens to match the correct height.
Use the following tree instead:
1 A
2 / \
3 B D
4 /
5 CThe incorrect calculation is:
11 + height(B) + height(D)
2= 1 + 1 + 0
3= 2For a deeper left chain, the sum keeps counting branches that cannot belong to one root-to-leaf path. Height must follow one longest path.
Correction:
1return 1 + max(leftHeight, rightHeight)height(null) = 0 with the same recurrenceIncorrect base case:
1if root = null
2 return 0Exposing input:
1AThe calculation becomes:
1height(A) = 1 + max(0, 0) = 1But a leaf has zero downward edges.
Correction: keep the edge-based convention consistent.
1height(null) = -1Then:
1height(A) = 1 + max(-1, -1) = 0Incorrect assumption:
1A single-node tree has height 1 because it has one level.Exposing input:
1AThe tree has one node level, but it has zero edges on a path from A to a leaf.
Correction:
1height(A) = 0Use the same edge-based convention throughout: null is -1, leaf is 0.
Implement treeSize(root) and treeHeight(root) using the course convention height(null) = -1.
The executable tests verify:
The tested contract is that treeSize returns the number of non-null nodes and treeHeight returns the longest downward path measured in edges.
1class Node:
2 def __init__(self, value, left=None, right=None):
3 self.value, self.left, self.right = value, left, right
4
5def tree_size(root):
6 if root is None:
7 return 0
8 return 1 + tree_size(root.left) + tree_size(root.right)
9
10def tree_height(root):
11 if root is None:
12 return -1 # edge-based: a leaf gets 1 + max(-1, -1) = 0
13 return 1 + max(tree_height(root.left), tree_height(root.right))
14
15root = Node("A", Node("B", Node("D"), Node("E")), Node("C"))
16print("size =", tree_size(root))
17print("height =", tree_height(root))
18print("single node height =", tree_height(Node("A")))
19print("empty tree height =", tree_height(None))1public class Main {
2 static class Node {
3 String value;
4 Node left, right;
5 Node(String value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
6 Node(String value) { this(value, null, null); }
7 }
8
9 static int treeSize(Node root) {
10 if (root == null) return 0;
11 return 1 + treeSize(root.left) + treeSize(root.right);
12 }
13
14 static int treeHeight(Node root) {
15 if (root == null) return -1; // edge-based: a leaf gets 1 + max(-1, -1) = 0
16 return 1 + Math.max(treeHeight(root.left), treeHeight(root.right));
17 }
18
19 public static void main(String[] args) {
20 Node root = new Node("A", new Node("B", new Node("D"), new Node("E")), new Node("C"));
21 System.out.println("size = " + treeSize(root));
22 System.out.println("height = " + treeHeight(root));
23 System.out.println("single node height = " + treeHeight(new Node("A")));
24 System.out.println("empty tree height = " + treeHeight(null));
25 }
26}1#include <algorithm>
2#include <iostream>
3#include <string>
4using namespace std;
5
6struct Node {
7 string value;
8 Node *left, *right;
9 Node(string v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
10};
11
12int treeSize(Node* root) {
13 if (!root) return 0;
14 return 1 + treeSize(root->left) + treeSize(root->right);
15}
16
17int treeHeight(Node* root) {
18 if (!root) return -1; // edge-based: a leaf gets 1 + max(-1, -1) = 0
19 return 1 + max(treeHeight(root->left), treeHeight(root->right));
20}
21
22int main() {
23 Node d("D"), e("E"), c("C");
24 Node b("B", &d, &e);
25 Node root("A", &b, &c);
26 Node single("A");
27 cout << "size = " << treeSize(&root) << endl;
28 cout << "height = " << treeHeight(&root) << endl;
29 cout << "single node height = " << treeHeight(&single) << endl;
30 cout << "empty tree height = " << treeHeight(nullptr) << endl;
31}1class Node {
2 constructor(value, left = null, right = null) {
3 this.value = value;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function treeSize(root) {
10 if (root === null) return 0;
11 return 1 + treeSize(root.left) + treeSize(root.right);
12}
13
14function treeHeight(root) {
15 if (root === null) return -1; // edge-based: a leaf gets 1 + max(-1, -1) = 0
16 return 1 + Math.max(treeHeight(root.left), treeHeight(root.right));
17}
18
19const root = new Node('A', new Node('B', new Node('D'), new Node('E')), new Node('C'));
20console.log(`size = ${treeSize(root)}`);
21console.log(`height = ${treeHeight(root)}`);
22console.log(`single node height = ${treeHeight(new Node('A'))}`);
23console.log(`empty tree height = ${treeHeight(null)}`);Take the height of each child subtree, keep the larger one and add 1 for the edge to that child. A null child returns -1, so a leaf returns 1 + max(-1, -1) = 0.
Depth counts edges from the root down to a node. Height counts edges from a node down to its deepest leaf. In the example tree, D has depth 2 and height 0, while A has depth 0 and height 2.
Height here counts edges. If null returned 0, a leaf would get 1 + max(0, 0) = 1, but a leaf has no downward edges. Using -1 makes a leaf 0 and keeps the formula uniform.
With edges, it is 0. Some sources count nodes along the path, which gives 1. Pick one convention and keep it across your base case and your answers.
Yes. Run a level order traversal and count the levels. The height in edges is the number of levels minus 1. This uses O(w) queue space instead of O(h) stack.