Skip to main content

78. Binary Tree Level Order Traversal II

mediumAsked at Ola

Return the bottom-up level-order traversal of a binary tree.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. From left to right, level by level from leaf to root.

Constraints

  • Number of nodes is in [0, 2000]
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[15,7],[9,20],[3]]

Example 2

Input
root = []
Output
[]

Approaches

1. BFS then reverse

Run normal level order and reverse the final array.

Time
O(n)
Space
O(n)
// reuse levelOrder then .reverse() at the end

Tradeoff:

2. BFS with prepend

Maintain an output array; unshift each level to push it to the front.

Time
O(n^2) due to unshift
Space
O(n)
function levelOrderBottom(root) {
  if (!root) return [];
  const out = [], q = [root];
  while (q.length) {
    const size = q.length, level = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift();
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    out.unshift(level);
  }
  return out;
}

Tradeoff:

Ola-specific tips

Ola interviewers ask whether you'd reverse or prepend; tie it to producing a leaf-to-root broadcast order for cleaning up a finished dispatch tree.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Binary Tree Level Order Traversal II and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →