Binary Tree Level Order Traversal II

Medium
1909.

Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II is a medium coding problem on breadth-first search and trees, asked in Amazon and Microsoft interviews.

Given the root of a binary tree, return its node values level by level from the bottom up: the deepest level first and the root's level last, each level read from left to right.

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[15,7],[9,20],[3]]
Explanation
The deepest level (15, 7) comes first and the root's level last; each level still reads left to right.

Example 2

Input
root = [1]
Output
[[1]]
Explanation
A single node is a single level.

Example 3

Input
root = []
Output
[]
Explanation
An empty tree has no levels.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Level Order Traversal II — Problem & Solution

Binary Tree Level Order Traversal II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Level Order Traversal II is a medium coding problem on breadth-first search and trees, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Breadth-First Search, Trees
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, return its node values level by level from the bottom up: the deepest level first and the root's level last, each level read from left to right.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Explanation: The deepest level (15, 7) comes first and the root's level last; each level still reads left to right.

Example 2

Input: root = [1]
Output: [[1]]
Explanation: A single node is a single level.

Example 3

Input: root = []
Output: []
Explanation: An empty tree has no levels.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= Node.val <= 1000

Hints for Binary Tree Level Order Traversal II

  1. Hint 1

    The levels themselves are the ordinary top-down level-order ones — only their order in the answer changes.

  2. Hint 2

    Collect the levels top-down with a breadth-first queue, one list per level.

  3. Hint 3

    Reverse the list of levels at the end (not the values inside each level).

How to solve Binary Tree Level Order Traversal II

Bottom-up order is top-down level order with the list of levels reversed, so do a normal breadth-first traversal and reverse once at the end.

Approach

  1. If the tree is empty, return an empty list.
  2. Process the tree level by level with a queue, children added left before right, appending one list of values per level.
  3. Reverse the order of the lists and return them.

Why it works

The breadth-first traversal produces each level's values left to right, in order of depth; reversing the outer list puts the deepest level first without touching the left-to-right order inside a level.

Complexity

  • Time — O(n)
  • Space — O(w) for the queue, w the largest number of nodes on one level (plus the output)

Pitfalls

  • Reverse the list of levels, not the values within each level.
  • Inserting every level at the front of an array list costs O(L^2) moves; collect then reverse once.

Reference solution

Python

from typing import List, Optional

def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:
    out = []
    level = [root] if root else []
    while level:
        out.append([node.val for node in level])
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    out.reverse()
    return out

Java

public static int[][] levelOrderBottom(TreeNode root) {
    List<int[]> out = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        int[] row = new int[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            row[i] = node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        out.add(row);
    }
    Collections.reverse(out);
    return out.toArray(new int[0][]);
}

C++

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

JavaScript

var levelOrderBottom = function(root) {
    var out = [];
    if (root === null) return out;
    var queue = [root], head = 0;
    while (head < queue.length) {
        var end = queue.length, row = [];
        while (head < end) {
            var node = queue[head++];
            row.push(node.val);
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        out.push(row);
    }
    return out.reverse();
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals