Subtree Height Evaluator Optimizer 7 — Problem Statement & Solution Guide
Problem Description
You are given a binary tree described by a level‑order traversal. The traversal is provided as a list of integers where the value -1 represents a missing child. The first element of the list is the root of the tree. For each node at index i (0‑based), its left child is at index 2*i+1 and its right child is at index 2*i+2 if those indices exist and the value at that index is not -1. Your task is to compute the height of the tree, defined as the number of nodes on the longest path from the root down to a leaf. The height of an empty tree is considered to be 0.
**Input**
The first line contains an integer n – the number of elements in the level‑order list. The second line contains n space‑separated integers representing the tree.
**Output**
Print a single integer – the height of the tree.
**Note**
The tree may be unbalanced and may contain up to 10^5 nodes. The values of the nodes are irrelevant for the height calculation; only the structure matters.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subtree Height Evaluator Optimizer 7"
WHY DOES IT MATTER?
Evaluating subtree heights is a fundamental tree DP pattern. It appears in balance‑checking, diameter calculation, and many hierarchical metric problems. Mastering this pattern teaches you how to exploit overlapping sub‑problems in recursive structures, a skill transferable to graphs, DP, and memoization tasks.
OPTIMIZATION CHALLENGE
The key insight is to process children before their parent (post‑order). By returning the child heights upward, each edge is examined once, eliminating the repeated traversals that plague the naïve method. This bottom‑up DP reduces time from quadratic to linear.
REAL-WORLD CONNECTION
Think of a corporate org chart where each manager's "span of control depth" equals the longest chain of reports beneath them. Computing this depth for every manager in one sweep mirrors the subtree height evaluation, enabling quick insights for restructuring or load‑balancing decisions.
When coding under interview pressure, write a helper that takes an index and returns height. Guard against -1 (null) early, and use memoization only if you convert to a node list; otherwise the recursion stack already provides O(H) space, which is optimal.
COMPLEXITY AT A GLANCE
O(N)O(H)Core Theory — Why This Approach?
The height of a subtree is defined as the number of edges on the longest downward path between that node and a leaf. Computing this value for every node in a binary tree can be expressed as a classic post‑order traversal problem: the height of a node equals 1 + max(height(left), height(right)). A naive solution that recomputes heights from scratch for each node leads to O(N²) time on skewed trees because each subtree is visited repeatedly. The optimal paradigm leverages the overlapping sub‑problems property of trees and applies a single depth‑first search (DFS) that returns the height to its parent while simultaneously storing the result for the current node. This bottom‑up approach guarantees each edge is processed exactly once, yielding linear time.
When the tree is supplied as a level‑order array with sentinel -1 for missing children, the algorithm first converts the implicit representation into an explicit node structure or works directly with indices. The conversion step is O(N) and does not affect the overall complexity. By using recursion (or an explicit stack) that respects the index arithmetic (left = 2*i+1, right = 2*i+2), we can compute heights without extra memory for adjacency lists, keeping the space usage to O(H) where H is the tree height (the recursion stack). This optimal solution scales to the maximum input size allowed by typical coding platforms (up to 10⁵ nodes).
Interview Questions on This Problem
Q1How would you compute the height of every subtree in a binary tree given as a level‑order array with -1 placeholders?
Perform a post‑order DFS using the index relationships (left = 2*i+1, right = 2*i+2). For each valid index, recursively obtain the heights of its children, set current height = 1 + max(leftHeight, rightHeight), and store it. Return the height to the caller. This runs in O(N) time and O(H) auxiliary space.
Q2Why does a naïve approach that recomputes height for each node individually result in O(N²) time on a skewed tree?
In a skewed tree, the height of the root equals N‑1. If we compute height for each node by traversing its entire subtree, the first node visits N nodes, the second visits N‑1, and so on, leading to the sum N + (N‑1) + … + 1 = O(N²). Overlapping sub‑problems cause repeated work.
Q3Can you modify the algorithm to also return the node(s) with the maximum subtree height in a single pass?
Yes. While computing heights, keep a global variable tracking the maximum height seen so far and a list of node indices achieving it. Update this pair whenever a node's computed height exceeds the current maximum or matches it, thus obtaining the answer without extra traversals.
Examples
Input
7 1 2 3 4 5 6 7
Output
3
Explanation: The tree is a perfect binary tree of height 3. The root (1) has two children (2,3). Each of those children has two children: 2 has (4,5) and 3 has (6,7). The longest path from root to leaf contains 3 nodes: 1→2→4 (or any other leaf).
Input
5 10 20 -1 -1 30 -1 -1
Output
3
Explanation: Root 10 has a left child 20 and no right child. Node 20 has a right child 30. The longest path is 10→20→30, which contains 3 nodes, so the height is 3.
Input
4 5 -1 6 -1 -1
Output
2
Explanation: Root 5 has no left child and a right child 6. Node 6 has no children. The longest path is 5→6, containing 2 nodes, so the height is 2.
Constraints
- 1 <= n <= 100000
- -1000000000 <= value of each node <= 1000000000
- -1 is used exclusively to denote a missing child
Optimal Approach & Strategy
Perform a single post‑order DFS that returns the height of each subtree to its parent, computing all heights in one pass.
Brute Force Approach
For each node, traverse its entire subtree to count the longest path, repeating this for every node.
Verified Code Solutions
function solution(root) {
if (!root) return 0;
let left = solution(root.left);
let right = solution(root.right);
return Math.max(left, right) + 1;
}class Solution {
public:
int solution(TreeNode* root) {
if (!root) return 0;
int left = solution(root->left);
int right = solution(root->right);
return max(left, right) + 1;
}
}class Solution {
public int solution(TreeNode root) {
if (root == null) return 0;
int left = solution(root.left);
int right = solution(root.right);
return Math.max(left, right) + 1;
}
}def solution(root):
if not root:
return 0
left = solution(root.left)
right = solution(root.right)
return max(left, right) + 1function solution(root) {
if (!root) return 0;
let left = solution(root.left);
let right = solution(root.right);
return Math.max(left, right) + 1;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.