3. Height of Binary Tree

The problem can be found at the following link: Problem Link

Problem Description

Given a binary tree, find its height. The height of a tree is defined as the number of edges on the longest path from the root to a leaf node. A leaf node is a node that does not have any children.

Examples

Example 1: Input: root[] = [12, 8, 18, 5, 11]

Output: 2 Explanation: One of the longest paths from the root (node 12) goes through node 8 to node 5, which has 2 edges.

Example 2: Input: root[] = [1, 2, 3, 4, N, N, 5, N, N, 6, 7]

Output: 3 Explanation: The longest path from the root (node 1) to a leaf node (node 6) contains 3 edges.

Constraints:

• 1 <= number of nodes <= $10^5$

• 0 <= node->data <= $10^5$

My Approach

We can solve the problem using recursion by computing the height of the left and right subtrees and taking the maximum of the two.

• Recursive DFS (Top-Down): Traverse the tree and for each node, return 1 + max(height(left), height(right)).

• Iterative BFS (Level Order): Use a queue to perform level order traversal and count the number of levels.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N), as each node is visited exactly once.

• Expected Auxiliary Space Complexity: O(H), where H is the height of the tree (space used in the recursion stack).

1️⃣ Recursive DFS (Top-Down)

Code (C)

int max(int a,int b){return a>b?a:b;}
int height(struct Node* node){return node?1+max(height(node->left),height(node->right)):-1;}

Code (C++)

class Solution {
public:
    int height(Node* node) {
        return node ? 1 + max(height(node->left), height(node->right)) : -1;
    }
};

🌲 Alternative Approaches

2️⃣ Iterative BFS (Level Order)

class Solution {
public:
    int height(Node* root) {
        if (!root) return -1;
        queue<Node*> q({root});
        int h = -1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; i--) {
                Node* n = q.front(); q.pop();
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            }
            h++;
        }
        return h;
    }
};

3️⃣ Recursive DFS (Bottom-Up)

class Solution {
public:
    int height(Node* node) {
        if (!node) return -1;
        int l = height(node->left), r = height(node->right);
        return 1 + max(l, r);
    }
};

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Method	Pros	Cons
Recursive DFS (Top-Down)	🟢 O(N)	🟡 O(H)	Recursion	Simple and concise	May cause stack overflow for deep trees
Iterative BFS (Level Order)	🟢 O(N)	🔴 O(W)	Queue-based	Avoids deep recursion issues	Higher memory usage for wide trees
Recursive DFS (Bottom-Up)	🟢 O(N)	🟡 O(H)	Recursion	Explicit computation, similar to Top-Down	Recursion stack usage remains

Best Choice?

• For balanced trees, Top-Down DFS is fine.

• For deep trees, BFS is better (avoids stack overflow).

• For clarity, Bottom-Up DFS is explicit and structured.

Code (Java)

class Solution {
    int height(Node node){
        return node == null ? -1 : 1 + Math.max(height(node.left), height(node.right));
    }
}

Code (Python)

class Solution:
    def height(self, root):
        return -1 if not root else 1 + max(self.height(root.left), self.height(root.right))

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count