Height of Special Binary Tree - Practice Coding Problems

Height of Special Binary Tree - Problem

You are given a root, which is the root of a special binary tree with n nodes. The nodes of the special binary tree are numbered from 1 to n.

Suppose the tree has k leaves in the following order: b₁ < b₂ < ... < bₖ. The leaves of this tree have a special property:

For every leaf bᵢ, the right child of bᵢ is bᵢ + 1 if i < k, and b₁ otherwise.
For every leaf bᵢ, the left child of bᵢ is bᵢ - 1 if i > 1, and bₖ otherwise.

Return the height of the given tree.

Note: The height of a binary tree is the length of the longest path from the root to any other node.

Input & Output

Example 1 — Basic Binary Tree

$ Input: root = [3,9,20,null,null,15,7]

› Output: 3

💡 Note: The longest path is from root to leaf: 3→20→15 or 3→20→7, both have length 3, so height is 3.

Example 2 — Simple Tree

$ Input: root = [1,2,3,4,5]

› Output: 2

💡 Note: Tree has 3 levels (0,1,2). Longest path is 1→2→4 or 1→2→5, both have length 2.

Example 3 — Single Node

$ Input: root = [1]

› Output: 0

💡 Note: Only root node exists, so height is 0 (no edges from root to itself).

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-100 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Find Paths

Identify all root-to-leaf paths and measure lengths

Maximum Length

Height equals the length of longest path

Key Takeaway

🎯 Key Insight: Tree height is the maximum number of edges from root to the deepest leaf node

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to find the longest path from root to any leaf node. Best approach uses DFS recursion to calculate maximum depth by exploring left and right subtrees. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Early Pruning	O(n)	O(h)	Enhanced DFS that avoids unnecessary recursive calls
Breadth-First Search	O(n)	O(w)	Level-by-level traversal to count tree levels
Brute Force DFS	O(n)	O(h)	Recursively explore all paths and track maximum depth

Optimized DFS with Early Pruning — Algorithm Steps

Start DFS from root
Track current maximum depth
Optimize recursive calls to avoid redundant work
Return maximum depth efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Leaf

Detect leaf nodes early to optimize

Smart Recursion

Only recurse on non-null children

Maximum Depth

Return optimal depth efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int maxDepth(struct TreeNode* node) {
    if (!node) return 0;
    
    if (!node->left && !node->right) return 1;
    
    int leftDepth = node->left ? maxDepth(node->left) : 0;
    int rightDepth = node->right ? maxDepth(node->right) : 0;
    
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return maxDepth(root) - 1;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Still need to visit each node to find maximum depth

✓ Linear Growth

Space Complexity

O(h)

Recursion depth equals tree height h

✓ Linear Space

78.5K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with Early Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler