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 Alex Chen, 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.

Practice these live with InterviewChamp.AI

Drill Find Leaves of Binary Tree and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →