Understanding the Problem
We are given a binary tree, and our task is to find its height. But what does "height" mean here?
The height of a binary tree is defined as the number of edges on the longest path from the root node down to the farthest leaf node. Some people define it in terms of the number of nodes (in that case, it's the number of nodes on the longest path). We'll use the number of nodes convention here, meaning the height of a tree with only the root node is 1.
We’ll now walk through a simple and intuitive example and build our understanding step by step.
Step-by-Step Solution with Example
Step 1: Understand the Tree Structure
Consider the binary tree represented like this:
1
/ 2 3
/
4
This tree has the following structure:
- Root node is 1
- Node 1 has two children: 2 (left) and 3 (right)
- Node 2 has one child: 4 (left)
- Nodes 3 and 4 are leaf nodes (no children)
Step 2: Use Recursion to Compute Height
We’ll calculate the height recursively:
- Start at the root node (1)
- Recursively compute the height of left subtree (node 2 → 4)
- Recursively compute the height of right subtree (node 3)
- Take the maximum of the two, and add 1 (for the current node)
So:
- Height of node 4 = 1 (leaf)
- Height of node 2 = 1 + height of node 4 = 2
- Height of node 3 = 1 (leaf)
- Height of root node (1) = 1 + max(2, 1) = 3
Final height = 3
Step 3: Implement the Recursive Function
public int height(TreeNode root) {
if (root == null) return 0;
int left = height(root.left);
int right = height(root.right);
return 1 + Math.max(left, right);
}
Edge Cases
Case 1: Empty Tree
If the root node is null
, then the tree is empty and its height is 0.
Case 2: Tree with Only One Node
Height is 1 since only the root exists.
Case 3: Left-Skewed Tree
1
/
2
/
3
Each node has only a left child. The height equals the number of nodes: 3.
Case 4: Right-Skewed Tree
1
2
3
Each node has only a right child. The height is also 3.
Case 5: Balanced Tree
1
/ 2 3
/ 4 5
This tree has 3 levels, so the height is 3.
Finally
Calculating the height of a binary tree is one of the most common and foundational problems in tree data structures. Once you understand the recursive nature of trees, this problem becomes intuitive. Always consider edge cases like empty trees, skewed trees, and single-node trees while designing your solution.
As a beginner, remember: recursion often mirrors the structure of the tree itself. Think of each node as its own mini-tree asking, “What’s the height of my children?”
Comments
Loading comments...