Questions
25 of 26
How do you find the diameter of a Binary Tree?
Difficulty: 6/10
tree traversal, depth-first search, recursive algorithms
Binary Tree Diameter
The diameter is the longest path between any two nodes in the tree. A key observation is that for each node, a candidate diameter passes through that node and has length equal to the height of its left subtree plus the height of its right subtree. A postorder traversal computes subtree heights bottom-up while maintaining the maximum diameter.
javascript
- 1
Use postorder traversal.
- 2
Height is computed once for every node.
- 3
Time complexity: O(n).
- 4
Auxiliary recursion space: O(h).
- 5
If diameter is defined in nodes rather than edges, add one to the edge-based result for a non-empty tree.
Scenario Questions
0-2 years experience
- 1We have a small binary tree representing a company's org chart with 7 nodes. How would you write a function to compute its diameter?
- 2If you accidentally swapped left and right child pointers in your recursion, what would happen to the diameter calculation?
2-5 years experience
- 1Your team is adding a feature that needs the longest path between any two nodes in a binary tree stored in a database. How would you implement the diameter calculation, and what trade‑offs would you consider regarding recursion vs. iterative approaches?
- 2During a code review you notice the diameter function runs in O(N^2) for certain inputs. How would you debug and improve its performance?
5-8 years experience
- 1Our service processes millions of tree structures per second and needs the diameter for each. How would you redesign the algorithm to handle this scale, considering memory usage and parallelism?
- 2If the tree can be modified concurrently by other threads while you compute its diameter, what synchronization or lock‑free strategies would you employ?
8+ years experience
- 1We are migrating a legacy system that stores hierarchical data in a relational DB to a graph service. The new service must expose an API to get the diameter of any subtree. How would you design the overall architecture to compute diameters efficiently while supporting frequent updates?
- 2Across multiple teams, the definition of 'diameter' has diverged (some count edges, others count nodes). How would you lead a cross‑team effort to standardize the metric and refactor existing codebases without breaking downstream services?
Follow-up Questions
- How would you adapt the solution to also return the actual longest path?
- What is the space complexity, and can it be reduced further?
- How does the algorithm change if the tree is stored as parent pointers instead of child pointers?