How Tall Is Your Tree?

How Tall is That Tree? Measuring Binary Tree Height the Right Way

Today’s problem: Find the height (or max depth) of a binary tree.

Sounds simple, but there are multiple ways to approach it – from level-wise BFS to elegant recursive DFS. Let's explore both styles and understand the trade-offs.

The Best Data Structure for Solving It (And Why!)

When it comes to measuring tree height, you need a structure that can navigate through nodes efficiently.

  • For level-order traversal, we use a Queue – because it helps traverse breadth-first (level by level).

  • For depth-first traversal, recursion does the heavy lifting with the call stack acting as your implicit data structure.

So both BFS and DFS are valid – it depends on how you want to walk the tree!

Different Approaches – Brute Force to Optimized Solutions

1. Recursive DFS (Post-order)

This is the cleanest and most intuitive way. You go all the way down to the leaves, and count your way back up.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lh = maxDepth(root.left);
        int rh = maxDepth(root.right);
        return Math.max(lh, rh) + 1;
    }
}

Explanation:

  • Get the depth of left and right subtrees.

  • Take the maximum of the two and add 1 for the current node.

2. Iterative BFS (Level Order)

This method counts the number of levels using a queue.


import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static int heightOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        int level = 0;
        q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode front = q.poll();
                if (front.left != null) {
                    q.add(front.left);
                }
                if (front.right != null) {
                    q.add(front.right);
                }
            }
            level++;
        }

        return level;
    }
}

Explanation:

  • Traverse the tree level by level.

  • For each level, increment the counter until all nodes are visited.

⚠️ Common Mistakes & Pitfalls to Avoid

  • Using the wrong class (Node instead of TreeNode) can cause compilation errors.

  • Forgetting to check for null roots will lead to runtime errors.

  • Not incrementing level correctly in BFS can give incorrect height.

📊 Time and Space Complexity Analysis

Recursive DFS

  • Time: O(n) – every node is visited once

  • Space: O(h) – height of the recursion stack (can be up to n for skewed trees)

Iterative BFS

  • Time: O(n) – every node is enqueued and dequeued once

  • Space: O(n) – worst case if the last level has n/2 nodes in queue

🌍 Real-World Applications

  • Rendering UIs: Layout trees in mobile/web dev often require max depth for rendering.

  • Game AI: Tree search algorithms like Minimax use depth limits.

  • Network design: Tree height can model packet traversal or hierarchy depth in system architecture.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Pascal's Triangle

 Pascal Vibes — Building Triangles Like a Pro Problem Statement Given an integer numRows , return the first numRows of Pascal's Triangle . Each number in the triangle is the sum of the two numbers directly above it . Example: Input: numRows = 5 Output: [ [ 1 ], [ 1,1 ], [ 1,2,1 ], [ 1,3,3,1 ], [ 1,4,6,4,1 ] ] Best Data Structure for Solving the Problem This is a CLASSIC example of Tabulation-based Dynamic Programming   We're filling a triangle row-by-row where: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] So we’ll use: A 2D List<List<Integer>> (or array of arrays) No need for fancy trees, heaps, or graphs here. Just pure math and memory  Different Approaches (from Brute Force to Optimized) Approach 1: Build Row by Row Using Previous Row This is the “OG” method — intuitive and easy to visualize. Start with [1] For each new row: Add 1 at the start and end In-between values are sum of two values above it class ...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Tower of Hanoi Modified

Tower of Hanoi Modified – When the First Rod is a No-Go Problem Statement You’re given a classic Tower of Hanoi setup with three rods (A, B, and C) and N disks of different sizes stacked on Rod A , smallest on top. BUT there’s a twist... You cannot move a disk directly between rod A and rod C. You must always pass through rod B when going from A ➡️ C or C ➡️ A.  Goal: Move all disks from Rod A to Rod C , following the usual rules plus this new restriction, and print: The minimum number of moves required. The actual sequence of moves (formatted like Move x from A to B ). Example Input: 2 1 2 Output: 2 Move 1 from A to B Move 1 from B to C 8 Move 1 from A to B Move 1 from B to C Move 2 from A to B Move 1 from C to B Move 1 from B to A Move 2 from B to C Move 1 from A to B Move 1 from B to C Best Data Structure for the Job No need for trees, heaps, or graphs here. Just: Simple recursion  Strings to log ea...
Read more