Max Height Calculation — Problem Statement & Solution Guide
Problem Description
Given a tree structure represented as a dictionary where each key is a node identifier and its corresponding value is a list of its child nodes, calculate the maximum height of the tree using recursion.
Examples
Input
{"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"], "E": ["B", "C"], "F": ["D", "E"], "G": ["A"], "H": ["A"]}Output
3
Explanation: Step-by-step: 1. Calculate height of node F: max height of D and E + 1 = max(2, 2) + 1 = 3. 2. Calculate height of node G and H: max height of A + 1 = 2. 3. Since F has the maximum height, the maximum height of the tree is 3.
Input
{"X": []}Output
1
Explanation: Step-by-step: 1. Calculate height of node X: max height of its children + 1 = 0 + 1 = 1. 2. The maximum height of the tree is 1.
Constraints
- Each system has a unique identifier.
- The input graph is a tree (no cycles).
- The maximum number of systems is 100.
Optimal Approach & Strategy
The optimal approach utilizes recursion to calculate the maximum height of the galaxy, where each system's height is determined by the maximum height of its orbiting systems plus one, leading to a time complexity of O(n).
Brute Force Approach
A brute-force approach would involve manually traversing each possible path in the galaxy and calculating its height, resulting in a time complexity of O(n^2) due to the nested iterations. This method is inefficient and impractical for large inputs.
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.