Daily Coding Challenge: Height of a Binary Tree

Picture yourself in a technical interview at LinkedIn. The interviewer sketches a binary tree on the whiteboard and asks, "How would you find its height?" This seemingly simple question is actually testing several important concepts: your understanding of tree structures, recursive thinking, and edge case handling. It's a classic warm-up problem that I've seen countless candidates either ace or stumble on, depending on their preparation.

Why This Problem Matters

The height of a binary tree problem appears frequently in technical interviews because it tests fundamental skills that transfer to more complex tree problems. Companies like LinkedIn, Microsoft, and Google often start with this question before moving to harder tree manipulation problems. Master this, and you'll have a solid foundation for tackling more advanced tree algorithms.

Binary Trees: A Quick Primer

Before we dive into the solution, let's refresh our understanding of binary trees. A binary tree is a hierarchical data structure where each node has at most two children, typically called the left and right child.

Key concepts to remember:

• Root: The topmost node (node 1 in our example)
• Leaf: A node with no children (nodes 4 and 5)
• Height: The number of nodes on the longest path from root to leaf
• Depth: The distance from the root to a specific node

Think of a binary tree like a family tree or organizational chart - there's a clear hierarchy, and we can trace paths from the top to any member.

Understanding the Problem

Let's break down what we're being asked to do:

Given: A root node of a binary tree

Find: The height of the tree

Important: An empty tree has height 0, a single node has height 1

Here's an example from our problem:

The longest paths (1 -> 3 -> 4) and (1 -> 3 -> 5) both have 3 nodes, so Height = 3

The key insight here is that the height is determined by the longest path from root to any leaf. In this case, we have two paths of length 3: 1 -> 3 -> 4 and 1 -> 3 -> 5.

Edge Cases to Consider

1. Empty tree (null root): Height = 0
2. Single node: Height = 1
3. Skewed tree (all nodes on one side): Height equals number of nodes
4. Balanced tree: Height is logarithmic to the number of nodes

Solution Approach

Let's think about this problem intuitively. If I asked you to find the tallest person in a group, you'd compare everyone's height and pick the maximum. Finding tree height works similarly - we need to find the maximum depth among all paths.

Building Intuition

Imagine you're standing at the root of the tree. To find the height:

1. Ask your left child: "What's your height?"
2. Ask your right child: "What's your height?"
3. Your height = 1 + max(left child's height, right child's height)

This naturally leads us to a recursive solution!

The Recursive Insight

The height of a binary tree is the number of nodes in its longest path from the root to its deepest leaf node. Talking recursively, when at the root node, the height of the binary tree is 1 + the maximum of the height of the left and right subtrees.

Pro tip: When solving tree problems, always think recursively first. Trees have a natural recursive structure that makes recursive solutions elegant and intuitive.

Implementation

Here's our solution in Java:

public class Solution {
  public int getHeight(TreeNode root) {
    // Base case: empty tree has height 0
    if (root == null) {
      return 0;
    }

    // Recursive case: height is 1 (current node) + max height of subtrees
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));
  }
}

Let's trace through our example to see how this works:

(See the full animation at https://firecode.io/firelogs/problems/31/height-of-a-binary-tree/)

Step-by-step execution:
1. Start at root (1): getHeight(1)
2. Visit left child (2): getHeight(2) returns 1 (no children)
3. Visit right child (3): getHeight(3)
4. Visit left child of 3 (4): getHeight(4) returns 1 (no children)
5. Visit right child of 3 (5): getHeight(5) returns 1 (no children)
6. Node 3 returns: 1 + max(1, 1) = 2
7. Node 1 returns: 1 + max(1, 2) = 3

The beauty of this solution lies in its simplicity. Each node only needs to know the height of its subtrees to calculate its own contribution to the overall height.

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once to compute its height. Whether the tree is balanced or skewed, we must examine every node to ensure we don't miss the longest path. Therefore, the time complexity is O(n), where n is the number of nodes.

Space Complexity: O(log n) average, O(n) worst case

The space complexity comes from the recursive call stack:

• Best case (balanced tree): O(log n) - The recursion depth equals the tree height
• Worst case (skewed tree): O(n) - When all nodes form a single path

I've seen many candidates forget to mention the space complexity of recursion. Remember: recursive calls use stack space!

Common Pitfalls

Having interviewed hundreds of candidates, here are the most common mistakes I see:

1. Off-by-one errors: Forgetting that a single node has height 1, not 0
2. Null handling: Not properly handling the empty tree case
3. Confusing height with depth: Height counts nodes, depth counts edges
4. Non-recursive attempts: While possible iteratively, it's much more complex

Pro tip: Always clarify the definition of height with your interviewer. Some sources define it as the number of edges (not nodes) on the longest path.

Interview Tips

When solving this problem in an interview:

1. Start with clarifying questions:

   • "Should I count nodes or edges for height?"
   • "What should I return for an empty tree?"
   • "Can I assume the TreeNode class is already defined?"

2. Talk through your approach:

   • "I'll use recursion since trees have a recursive structure"
   • "My base case will handle null nodes"
   • "I'll recursively find the height of left and right subtrees"

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode.io, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you’re just starting or preparing for your dream job, mastering fundamentals like this will set you up for success.

Happy coding, and may all your trees be perfectly balanced! 🌳

1. Consider follow-up questions:

   • "How would you find the height iteratively?" (Use level-order traversal)
   • "What if we need to find height frequently?" (Consider caching)
   • "How would you find the diameter of the tree?" (Related problem)

2. If you get stuck:

   • Draw a small example (3-4 nodes)
   • Think about the base case first
   • Remember that tree problems often have elegant recursive solutions

Key Takeaway

The height of a binary tree problem teaches us a fundamental pattern in tree algorithms: combine results from subtrees to solve for the current node. This pattern appears in countless tree problems - from calculating sums to checking balance to finding paths. Master this recursive thinking, and you'll find many tree problems become much more approachable.

Practice Makes Perfect

This problem is just the beginning of your tree algorithm journey. Once you're comfortable with finding height, try these related problems to deepen your understanding:

• Find the minimum depth of a binary tree
• Check if a binary tree is balanced
• Find the diameter of a binary tree

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode.io, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering fundamentals like this will set you up for success.

Happy coding, and may all your trees be perfectly balanced! 🌳