← Meta Interview Insights

Meta·Backend Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Meta backend interview with a tree problem that looks manageable until you actually try to implement it cleanly. The boundary traversal question has a lot of edge cases that will eat you alive if you're not careful going in.

Questions Asked (1)

Q1

Given the root of a binary tree, return the values along its boundary in anti-clockwise order starting from the root. The boundary includes the left boundary (excluding leaves), all leaves left to right, and the right boundary in reverse (excluding leaves). Handle edge cases like single-node trees and trees with only one subtree.

Algorithms & Data Structures
Author's notes

I thought I had this.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Break the problem into three distinct traversals: left boundary (top-down, excluding leaves), leaves (left-to-right), and right boundary (bottom-up, excluding leaves). Use DFS to collect each part, then concatenate them while handling edge cases like single-node trees and skewed trees.

Pro tip: Clarify with the interviewer whether the root should be included only once and how to handle cases where the tree is skewed (e.g., only left or only right children). This shows attention to detail and avoids duplicate values.

1. Clarify and define boundaries

Confirm the definition of left boundary, right boundary, and leaves, and how to handle edge cases like single-node trees. Ensure the root is included only once.

2. Collect left boundary

Traverse from root's left child downwards, adding nodes that are not leaves. Prefer left child over right child when both exist.

3. Collect leaves

Perform a DFS (pre-order) to collect all leaf nodes from left to right. A leaf is a node with no children.

4. Collect right boundary

Traverse from root's right child downwards, adding non-leaf nodes, but store them in a list to reverse later (or use post-order). Prefer right child over left child.

5. Combine and handle edge cases

Concatenate root (if not already included), left boundary, leaves, and reversed right boundary. Handle cases where root is the only node or when one subtree is missing.

Key Points to Mention

  • Definition of left and right boundaries: nodes on the path from root to the leftmost/rightmost node, excluding leaves.
  • Leaf nodes are those with no children; collect them via DFS in left-to-right order.
  • Avoid duplicates: ensure root is added only once, and leaves are not included in left/right boundaries.
  • Edge cases: single-node tree (return [root]), skewed trees (only left or only right children), and trees where root is a leaf.
  • Time complexity: O(n) where n is number of nodes, as each node is visited at most twice.
  • Space complexity: O(h) for recursion stack, where h is tree height, plus O(n) for output.

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