Bottom-up level order binary tree traversal

You're in a Microsoft interview and the interviewer draws a binary tree on the whiteboard. "I want you to visit every node," they say, "but start from the bottom. Deepest level first, then work your way up to the root." You know how to do a standard level order traversal with BFS, but the bottom-up twist requires a small adaptation. This problem tests whether you can modify a familiar algorithm to meet a new constraint, and it shows up at Amazon, Apple, and Microsoft under the name Binary Tree Level Order Traversal II.

TL;DR

Perform a standard BFS using a queue, but enqueue each node's right child before its left child. Collect node values into a list as you dequeue them. After the queue is empty, reverse the list. The reversed output contains nodes from the deepest level to the root, left to right within each level. This runs in O(n) time and O(n) space.

Why This Problem Matters

Bottom-up level order traversal is a natural extension of the standard BFS pattern that shows up constantly in tree problems. Once you understand how to run BFS and then transform the output, you can tackle variants like zigzag traversal, level-by-level grouping, and right-side view. Interviewers like this problem because it tests both BFS mechanics and your ability to adapt an algorithm with minimal changes.

Binary Trees and Level Order Traversal: A Quick Primer

A binary tree is a hierarchical data structure where each node has at most two children (left and right). Level order traversal visits nodes one level at a time, typically from left to right.

In the tree above, a standard (top-down) level order traversal visits nodes as: [1, 2, 3, 4, 5]. The bottom-up version flips that: [4, 5, 2, 3, 1]. The deepest leaves come first, and the root comes last.

Key terminology:

• Level 0: The root node
• Level 1: Children of the root
• Level 2: Grandchildren of the root (the deepest level in this example)

Understanding the Problem

Given: The root of a binary tree Task: Traverse the tree bottom-up, level by level, going left to right within each level Return: A flat list of node values in the required order Constraints: The tree has between 1 and 100 nodes. Node values range from 0 to 1000.

Here is the example from the problem:

  tree: 1 2 3 # # 4 5

      1
     / \
    2   3
       / \
      4   5

  bottomUpLevelOrder(1 2 3 # # 4 5) -> [4, 5, 2, 3, 1]

The expected output starts with the bottom level [4, 5], then the middle level [2, 3], and ends with the root [1].

Edge Cases to Consider

1. Single node: The tree has only a root. Return [root.data].
2. Skewed tree: All nodes are on one side (like a linked list). Each "level" has one node, and the output reverses their order.
3. Complete binary tree: The widest level has the most nodes, and the queue reaches its maximum size there.

Solution Approach

Standard BFS processes nodes top-down. To get bottom-up output, there are two common strategies:

1. BFS + reverse: Run BFS as usual, collect output, then reverse the list.
2. BFS + stack: Push values onto a stack during BFS, then pop them off.

Both approaches have the same O(n) time and O(n) space complexity. The reverse approach is simpler and more common in interviews.

The Right-Before-Left Trick

There is a subtle detail that makes the reversal work cleanly. During BFS, if you enqueue the right child before the left child, the traversal order (before reversal) becomes: root, then right-to-left at each level. When you reverse that sequence, each level appears left-to-right, and the levels themselves are ordered bottom-to-top.

In this tree, enqueueing right before left at each step produces [1, 3, 2, 5, 4] before reversal. After reversing: [4, 5, 2, 3, 1], which is exactly the bottom-up level order.

Algorithm Walkthrough

Here is the step-by-step process for the example tree [1, 2, 3, #, #, 4, 5]:

Phase 1: BFS traversal (right child enqueued first)

1. Start with root (node 1) in the queue
2. Dequeue node 1, add its value to output, enqueue right child (3) then left child (2)
3. Dequeue node 3, add its value to output, enqueue right child (5) then left child (4)
4. Dequeue node 2, add its value to output (no children to enqueue)

Phase 2: Continue BFS and reverse

5. Dequeue nodes 5 and 4 (both are leaves with no children)
6. Queue is empty. Output before reversal: [1, 3, 2, 5, 4]
7. Reverse the list to get the final result: [4, 5, 2, 3, 1]

Verifying with a Balanced Tree

For the balanced tree [1, 2, 3, 4, 5, 6, 7], the expected output is [4, 5, 6, 7, 2, 3, 1].

The same pattern holds: BFS with right-before-left enqueue order, followed by a single reversal.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public List<Integer> bottomUpLevelOrder(TreeNode root) {
    // Create a queue for BFS traversal
    Queue<TreeNode> queue = new LinkedList<>();

    // Create an output list to store visited node values
    List<Integer> output = new ArrayList<>();

    // Seed the queue with the root node
    queue.add(root);

    // Process nodes until the queue is empty
    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();

      // Record the current node's value
      output.add(node.data);

      // Enqueue right child first, then left child
      // This ordering is important for the reversal step
      if (node.right != null) queue.add(node.right);
      if (node.left != null) queue.add(node.left);
    }

    // Reverse the list to get bottom-up, left-to-right order
    Collections.reverse(output);
    return output;
  }
}

The algorithm has three parts:

1. Initialize a queue with the root node and an empty output list.
2. BFS loop: Dequeue a node, record its value, enqueue its right child then left child.
3. Reverse the output list and return it.

The right-before-left enqueue order is the only difference from a standard level order traversal. If you enqueued left before right, the reversed output would have each level ordered right-to-left instead of left-to-right.

Complexity Analysis

Time Complexity: O(n)

Each of the n nodes is enqueued and dequeued exactly once, contributing O(n) work. The reversal at the end is also O(n). The total is O(n) + O(n) = O(n).

Space Complexity: O(n)

The output list stores all n node values. The queue can hold at most O(n/2) nodes at the widest level of a complete binary tree, which simplifies to O(n). Both the queue and the output list contribute O(n) space.

Alternative Approaches

• Stack-based: Use a stack instead of a list. Push values during BFS, then pop them all. Same complexity, slightly different code.
• Level-by-level collection with reversal: Collect nodes grouped by level (using a list of lists), then reverse the outer list. This is useful when the problem asks for grouped output like [[4, 5], [2, 3], [1]].
• Recursive BFS (unusual): You can simulate level order traversal recursively using DFS with a level parameter, but this is less intuitive and not what interviewers expect for this problem.

Common Pitfalls

1. Wrong enqueue order: Enqueueing left before right and then reversing gives right-to-left ordering within each level. Always enqueue right first when using the reverse approach.

2. Forgetting to reverse: Without the reversal step, the output is top-down right-to-left, not bottom-up left-to-right.

3. Null checks: Forgetting to check whether children are null before enqueueing. In languages like Java, enqueueing null and then calling node.data on it throws a NullPointerException.

4. Confusing this with DFS: This is a BFS problem. DFS (preorder, inorder, postorder) visits nodes along branches, not levels. BFS with a queue is the right tool here.

Interview Tips

When you see this problem in an interview:

1. Start by clarifying: "Should the output be a flat list of values, or grouped by level?" The Firecode version asks for a flat list, but some variants want List<List<Integer>>.

2. Mention the standard BFS connection: "This is standard level order traversal with a reversal at the end." That shows you recognize the pattern.

3. Explain the enqueue order: "I enqueue right before left so that after reversing, each level reads left to right." This is the key insight interviewers look for.

4. Discuss alternatives: Mention the stack-based approach as a one-liner: "I could also use a stack instead of reversing a list, but the asymptotic cost is the same."

5. Test with a small tree: Trace through a 3-node tree [1, 2, 3] to verify your logic before coding.

Key Takeaways

• Bottom-up level order traversal is BFS with one twist: reverse the output at the end. The core queue-based traversal is identical to standard level order.
• Enqueue the right child before the left child. When the output list is reversed, this produces left-to-right ordering within each level, which is the expected result.
• Time complexity is O(n) because each node is processed once and the reversal is linear. Space complexity is O(n) for the queue and the output list.
• This pattern extends to many related tree problems: zigzag traversal (alternate reversals per level), right-side view (take the last node per level), and level-width calculation.
• In an interview, always trace through a small example to verify the enqueue order and reversal logic before writing code.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def bottom_up_level_order(self, root):
        queue = deque()
        output = []

        queue.append(root)

        while len(queue) > 0:
            node = queue.popleft()
            output.append(node.data)

            if node.right is not None:
                queue.append(node.right)
            if node.left is not None:
                queue.append(node.left)

        output.reverse()
        return output

Python's deque provides O(1) popleft for efficient queue operations, compared to list.pop(0) which is O(n).

JavaScript

class Solution {
  bottomUpLevelOrder(root) {
    const queue = new Queue();
    const output = [];

    queue.enqueue(root);

    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      output.push(node.data);

      if (node.right !== null) queue.enqueue(node.right);
      if (node.left !== null) queue.enqueue(node.left);
    }

    return output.reverse();
  }
}

TypeScript

class Solution {
  bottomUpLevelOrder(root: TreeNode): number[] {
    const queue = new Queue<TreeNode>();
    const output: number[] = [];

    queue.offer(root);

    while (!queue.isEmpty()) {
      const node = queue.poll()!;
      output.push(node.data);

      if (node.right !== null) queue.offer(node.right);
      if (node.left !== null) queue.offer(node.left);
    }

    return output.reverse();
  }
}

C++

#include <queue>
#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<int> bottomUpLevelOrder(TreeNode *root) {
    std::vector<int> out;
    if (root == nullptr) return out;

    std::queue<TreeNode *> queue;
    queue.push(root);

    while (!queue.empty()) {
      TreeNode *node = queue.front();
      queue.pop();
      out.push_back(node->data);

      if (node->right != nullptr) queue.push(node->right);
      if (node->left != nullptr) queue.push(node->left);
    }

    std::reverse(out.begin(), out.end());
    return out;
  }
};

C++ uses std::queue which wraps a deque by default, and std::reverse from <algorithm> for the final reversal.

Go

func (s *Solution) BottomUpLevelOrder(root *TreeNode) []int {
    var out []int
    if root == nil {
        return out
    }

    queue := NewQueue()
    queue.Offer(root)

    for !queue.IsEmpty() {
        node := queue.Poll().(*TreeNode)
        out = append(out, node.Data)

        if node.Right != nil {
            queue.Offer(node.Right)
        }
        if node.Left != nil {
            queue.Offer(node.Left)
        }
    }

    // Reverse the slice in place
    for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
        out[i], out[j] = out[j], out[i]
    }
    return out
}

Go does not have a built-in reverse function, so the reversal uses a two-pointer swap.

Kotlin

import java.util.*

class Solution {
    fun bottomUpLevelOrder(root: TreeNode?): List<Int> {
        if (root == null) return emptyList()

        val queue: Queue<TreeNode> = LinkedList()
        val output = mutableListOf<Int>()

        queue.add(root)

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            output.add(node.data)

            if (node.right != null) queue.add(node.right)
            if (node.left != null) queue.add(node.left)
        }

        output.reverse()
        return output
    }
}

Scala

import scala.collection.mutable

class Solution {
  def bottomUpLevelOrder(root: TreeNode): List[Int] = {
    val queue = mutable.Queue[TreeNode]()
    val output = mutable.ArrayBuffer[Int]()

    queue.enqueue(root)

    while (queue.nonEmpty) {
      val node = queue.dequeue()
      output.append(node.data)

      if (node.right != null) queue.enqueue(node.right)
      if (node.left != null) queue.enqueue(node.left)
    }

    output.reverse.toList
  }
}

Swift

class Solution {
    func bottomUpLevelOrder(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }

        var queue: [TreeNode] = [root]
        var output: [Int] = []

        while !queue.isEmpty {
            let node = queue.removeFirst()
            output.append(node.data)

            if let right = node.right { queue.append(right) }
            if let left = node.left { queue.append(left) }
        }

        return Array(output.reversed())
    }
}

Ruby

class Solution
  def bottom_up_level_order(root)
    queue = []
    output = []

    queue.push(root)

    while !queue.empty?
      node = queue.shift
      output.push(node.data)

      queue.push(node.right) if node.right
      queue.push(node.left) if node.left
    end

    output.reverse
  end
end

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn bottom_up_level_order(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        let mut queue: VecDeque<&TreeNode> = VecDeque::new();
        let mut output: Vec<i32> = Vec::new();

        if let Some(ref node) = root {
            queue.push_back(node);
        }

        while let Some(node) = queue.pop_front() {
            output.push(node.data);

            if let Some(ref right) = node.right {
                queue.push_back(right);
            }
            if let Some(ref left) = node.left {
                queue.push_back(left);
            }
        }

        output.reverse();
        output
    }
}

Rust uses VecDeque for efficient double-ended queue operations and pattern matching with if let for null-safe child access.

C#

using System.Collections.Generic;

public class Solution {
    public List<int> BottomUpLevelOrder(TreeNode root) {
        var queue = new Queue<TreeNode>();
        var output = new List<int>();

        queue.Enqueue(root);

        while (queue.Count > 0) {
            var node = queue.Dequeue();
            output.Add(node.data);

            if (node.right != null) queue.Enqueue(node.right);
            if (node.left != null) queue.Enqueue(node.left);
        }

        output.Reverse();
        return output;
    }
}

Dart

class Solution {
  List<int> bottomUpLevelOrder(TreeNode? root) {
    if (root == null) return [];

    List<TreeNode> queue = [];
    List<int> output = [];

    queue.add(root);

    while (queue.isNotEmpty) {
      TreeNode node = queue.removeAt(0);
      output.add(node.data);

      if (node.right != null) queue.add(node.right!);
      if (node.left != null) queue.add(node.left!);
    }

    return output.reversed.toList();
  }
}

PHP

class Solution {
    public function bottomUpLevelOrder(?TreeNode $root): array {
        if ($root === null) { return []; }
        $queue = [$root];
        $output = [];

        while (!empty($queue)) {
            $node = array_shift($queue);
            $output[] = $node->data;

            if ($node->right !== null) $queue[] = $node->right;
            if ($node->left !== null) $queue[] = $node->left;
        }

        return array_reverse($output);
    }
}

Practice Makes Perfect

Once you're comfortable with bottom-up level order traversal, try these related problems to strengthen your BFS skills:

• Standard level order traversal (top-down)
• Zigzag level order traversal (alternating left-right and right-left per level)
• Binary tree right side view (the rightmost node at each level)
• Average of levels in a binary tree

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering BFS patterns like this one will serve you well.

Happy coding, and may your queues always be first-in, first-out!