Skip to main content

366. Find Leaves of Binary Tree

mediumAsked at LinkedIn

Given a binary tree, collect its leaves and remove them, then repeat. Return the order of removals. LinkedIn asks this because the elegant solution isn't iterative removal — it's a 'height from leaf' DFS that buckets each node by its eventual removal layer.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn SWE onsite reports list Find Leaves of Binary Tree among the high-frequency LinkedIn-tagged questions.
  • Blind (2025-11)— LinkedIn writeups specifically describe the 'height bucketing' trick as the explicit signal.

Problem

Given the root of a binary tree, collect a tree's nodes as if you were doing this: collect all the leaf nodes; remove all the leaf nodes; repeat until the tree is empty.

Constraints

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100

Examples

Example 1

Input
root = [1,2,3,4,5]
Output
[[4,5,3],[2],[1]]

Explanation: First, 4, 5, 3 are leaves. After removing them, 2 becomes a leaf. After removing 2, only 1 remains.

Example 2

Input
root = [1]
Output
[[1]]

Approaches

1. Iterative simulation — repeatedly find and remove leaves

Repeatedly walk the tree, collect leaves into a layer, set their parents' references to null, repeat until empty.

Time
O(n^2) worst case
Space
O(n)
function findLeavesSim(root) {
  const out = [];
  function isLeaf(node) { return !node.left && !node.right; }
  function pruneLeaves(node, layer) {
    if (!node) return null;
    if (isLeaf(node)) { layer.push(node.val); return null; }
    node.left = pruneLeaves(node.left, layer);
    node.right = pruneLeaves(node.right, layer);
    return node;
  }
  while (root) {
    const layer = [];
    root = pruneLeaves(root, layer);
    out.push(layer);
  }
  return out;
}

Tradeoff: Direct simulation. Each pass is O(n); total passes = max height; worst case O(n^2) for a skewed tree. Mention as baseline before the height-bucketing version.

2. Single-pass DFS computing height-from-leaf (optimal)

Define height(node) = max(height(left), height(right)) + 1 if leaf height is 1. Each node's height is its REMOVAL LAYER. Group nodes by height; that's the answer.

Time
O(n)
Space
O(n)
function findLeaves(root) {
  const out = [];
  function dfs(node) {
    if (!node) return 0;
    const h = Math.max(dfs(node.left), dfs(node.right)) + 1;
    while (out.length < h) out.push([]);
    out[h - 1].push(node.val);
    return h;
  }
  dfs(root);
  return out;
}

Tradeoff: O(n) — single traversal. The key insight: a node is removed in the round equal to max(its children's removal rounds) + 1. Pure leaves have height 1; their parents become leaves after the first removal, height 2; and so on.

LinkedIn-specific tips

LinkedIn interviewers grade whether you spot the height-bucketing trick. Articulate: 'A node's removal LAYER is exactly max(left height, right height) + 1 — where leaves have height 1. So I can group nodes by height in a single DFS.' That single sentence is the entire algorithm. The simulation version works but loses the signal — say 'I'll skip simulating and bucket by height directly.'

Common mistakes

  • Returning the leaves in some other order than 'lowest layer first' — LC checks layer order strictly.
  • Using 0-indexed height and not adjusting — gives off-by-one in the result array.
  • Trying to actually MUTATE the tree to find leaves — wastes time and doesn't pass when called twice on the same input.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

  • What if you needed to return the nodes in the order they were removed within each layer?
  • Find Leaves with subtree sums instead of values.
  • Find the longest 'leaf-chain' — same height calculation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does max(left, right) + 1 equal the removal layer?

Because a node can only be a leaf in the simulation when both its children are gone. If left children are removed by layer L and right by layer R, the node becomes a leaf at layer max(L, R), and is removed at layer max(L, R) + 1.

Could you do this with BFS?

Not naturally — BFS visits roots first, but the order of removal is leaves-first. A reverse-BFS variant works but the DFS height-bucketing is far simpler.

Free learning resources

Curated free links for this problem.

More LinkedIn coding interview questions

See all LinkedIn problems →