Binary Tree Level Order Traversal II

medium tree bfs

Problem

Given the root of a binary tree, return the bottom-up level order traversal — i.e., from leaves up to root, left to right within each level.

Inputroot = [3, 9, 20, null, null, 15, 7]

Output[[15, 7], [9, 20], [3]]

Top-down BFS produces [[3], [9, 20], [15, 7]]; reverse to get bottom-up.

level-order (use "null" for missing)

from collections import deque
def level_order_bottom(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out[::-1]

function levelOrderBottom(root) {
  if (!root) return [];
  const out = [], q = [root];
  while (q.length) {
    const level = [], size = q.length;
    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.push(level);
  }
  return out.reverse();
}

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            out.add(0, level);
        }
        return out;
    }
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> out;
    if (!root) return out;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        vector<int> level;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        out.push_back(level);
    }
    reverse(out.begin(), out.end());
    return out;
}

Explanation

"Bottom-up" sounds tricky, but it is just the normal top-down level order with the list of levels flipped at the end.

We run a standard BFS with a queue. At the start of each round, the queue holds exactly one level, so we freeze its size, pop that many nodes into a level list, and enqueue their children for the next round.

Each completed level is appended to out in top-to-bottom order, the same as ordinary level-order traversal.

The only twist is the final out[::-1] (or reverse) that turns the order upside down so leaves come first and the root comes last. The Java version achieves the same by inserting each level at the front with out.add(0, level).

Example: top-down gives [[3], [9,20], [15,7]]; reversing yields [[15,7], [9,20], [3]].

Time: O(n) Space: O(n)