← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Meta SWE coding round, one tree problem the whole time. Pretty focused session, they wanted the solution but also wanted me to explain the thinking behind it which I wasn't fully expecting.

Questions Asked (1)

Q1

Given the root of a binary tree, find the diameter, defined as the maximum number of edges on any path between two nodes. Does the path have to go through the root? Walk through your solution and analyze its time and space complexity. Also handle the edge cases for empty trees and single-node trees.

Algorithms & Data Structures
Author's notes

I knew the general idea going in but the 'does it pass through the root' part tripped me up for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS that returns the height of each subtree while updating a global maximum diameter. At each node, the longest path through that node is the sum of the heights of its left and right subtrees; update the global max accordingly. This handles all paths, not just those through the root, in O(n) time and O(h) space.

Pro tip: Clarify that the diameter is the number of edges, not nodes, and explicitly state that the path does not have to pass through the root. Mention that you can solve it in one pass without storing all node heights, which is more space-efficient.

1. Clarify the definition and edge cases

Confirm that diameter is the maximum number of edges on any path between two nodes, and that the path may or may not pass through the root. State that for an empty tree the diameter is 0, and for a single-node tree it is also 0.

2. Choose the right traversal

Use a post-order DFS (recursive or iterative) to compute the height of each subtree bottom-up. This allows you to evaluate the longest path through each node as you go.

3. Define the recursive relation

For a node, the longest path through it is leftHeight + rightHeight (in edges). The height returned to the parent is 1 + max(leftHeight, rightHeight). Update a global maximum with the path length at each node.

4. Implement and handle edge cases

Write the recursive function, initializing the global max to 0. For null nodes, return -1 (so that leaf nodes have height 0) or return 0 and adjust the path calculation accordingly. Ensure empty and single-node trees return 0.

5. Analyze complexity and test

State that the time complexity is O(n) because each node is visited once, and space complexity is O(h) for the recursion stack, where h is the tree height (O(n) worst case, O(log n) for balanced trees). Walk through a small example to verify.

Key Points to Mention

  • The diameter path does not have to pass through the root; it can be entirely within a subtree.
  • Use a post-order DFS to compute subtree heights and update the global diameter in one pass.
  • The longest path through a node is the sum of the heights of its left and right subtrees (in edges).
  • Time complexity is O(n) and space complexity is O(h) due to recursion stack.
  • Edge cases: empty tree returns 0, single-node tree returns 0.
  • Avoid recomputing heights by combining height calculation and diameter update in the same traversal.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.