Binary Tree Level Order Traversal

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values (left to right, level by level).

Examples

Input	Output
[3,9,20,null,null,15,7]	[[3],[9,20],[15,7]]
[1]	[[1]]
[]	[]

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space
BFS Queue	O(n)	O(w)
DFS with Level	O(n)	O(h)

Natural

BFS Queue

O(n) time · O(w) space

Recursive

DFS with Level

O(n) time · O(h) space

Approach 1: BFS Queue (Recommended)

★ Recommended

Use a queue to traverse level by level, collecting nodes at each level into a list.

⏱ Time O(n) Visit all nodes 💾 Space O(w) Queue width

Solution Code

Python

binary_tree_level_order_traversal_bfs.py

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root: return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(levelOrder(root))  # [[3], [9, 20], [15, 7]]

C++

binary_tree_level_order_traversal_bfs.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size(); vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        result.push_back(level);
    }
    return result;
}

Java

binary_tree_level_order_traversal_bfs.java

import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> q = new LinkedList<>(); q.offer(root);
        while (!q.isEmpty()) {
            int sz = q.size(); List<Integer> level = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            result.add(level);
        }
        return result;
    }

    public static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int x) { val = x; }
    }
}

JavaScript

binary_tree_level_order_traversal_bfs.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function levelOrder(root) {
    const result = []; if (!root) return result;
    const queue = [root];
    while (queue.length) {
        const sz = queue.length, level = [];
        for (let i = 0; i < sz; i++) {
            const n = queue.shift();
            level.push(n.val);
            if (n.left) queue.push(n.left);
            if (n.right) queue.push(n.right);
        }
        result.push(level);
    }
    return result;
}

module.exports = levelOrder;

Rust

binary_tree_level_order_traversal_bfs.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    if root.is_none() { return result; }
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());
    while !queue.is_empty() {
        let sz = queue.len();
        let mut level = Vec::new();
        for _ in 0..sz {
            let n = queue.pop_front().unwrap();
            let n_ref = n.borrow_mut();
            level.push(n_ref.val);
            if let Some(l) = n_ref.left.clone() { queue.push_back(l); }
            if let Some(r) = n_ref.right.clone() { queue.push_back(r); }
        }
        result.push(level);
    }
    result
}

Go

binary_tree_level_order_traversal_bfs.go

package main

type TreeNode struct { Val int; Left, Right *TreeNode }

func LevelOrder(root *TreeNode) [][]int {
    var result [][]int
    if root == nil { return result }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        sz := len(queue)
        level := make([]int, 0)
        for i := 0; i < sz; i++ {
            n := queue[0]
            queue = queue[1:]
            level = append(level, n.Val)
            if n.Left != nil { queue = append(queue, n.Left) }
            if n.Right != nil { queue = append(queue, n.Right) }
        }
        result = append(result, level)
    }
    return result
}

Approach 2: DFS with Level Tracking

🎯 Interview Favourite

Use DFS and track level, building result lists on demand.

⏱ Time O(n) Visit all nodes 💾 Space O(h) Call stack

Solution Code

Python

binary_tree_level_order_traversal_dfs.py

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    def dfs(node: Optional[TreeNode], level: int):
        if not node: return
        if level == len(result): result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(levelOrder(root))  # [[3], [9, 20], [15, 7]]

C++

binary_tree_level_order_traversal_dfs.cpp

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

void dfs(TreeNode* n, int level, vector<vector<int>>& result) {
    if (!n) return;
    if (level == result.size()) result.push_back({});
    result[level].push_back(n->val);
    dfs(n->left, level + 1, result);
    dfs(n->right, level + 1, result);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    dfs(root, 0, result);
    return result;
}

Java

binary_tree_level_order_traversal_dfs.java

import java.util.*;

public class Solution {
    void dfs(TreeNode n, int level, List<List<Integer>> result) {
        if (n == null) return;
        if (level == result.size()) result.add(new ArrayList<>());
        result.get(level).add(n.val);
        dfs(n.left, level + 1, result);
        dfs(n.right, level + 1, result);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    public static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int x) { val = x; }
    }
}

JavaScript

binary_tree_level_order_traversal_dfs.js

function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

function levelOrder(root) {
    const result = [];
    function dfs(n, level) {
        if (!n) return;
        if (level === result.length) result.push([]);
        result[level].push(n.val);
        dfs(n.left, level + 1);
        dfs(n.right, level + 1);
    }
    dfs(root, 0);
    return result;
}

module.exports = levelOrder;

Rust

binary_tree_level_order_traversal_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, level: usize, result: &mut Vec<Vec<i32>>) {
        if let Some(node) = n {
            let node_ref = node.borrow();
            if level == result.len() { result.push(Vec::new()); }
            result[level].push(node_ref.val);
            dfs(&node_ref.left, level + 1, result);
            dfs(&node_ref.right, level + 1, result);
        }
    }
    dfs(&root, 0, &mut result);
    result
}

Go

binary_tree_level_order_traversal_dfs.go

package main

type TreeNode struct { Val int; Left, Right *TreeNode }

func LevelOrder(root *TreeNode) [][]int {
    var result [][]int
    var dfs func(*TreeNode, int)
    dfs = func(n *TreeNode, level int) {
        if n == nil { return }
        if level == len(result) { result = append(result, []int{}) }
        result[level] = append(result[level], n.Val)
        dfs(n.Left, level + 1)
        dfs(n.Right, level + 1)
    }
    dfs(root, 0)
    return result
}

Related Problems

• Binary Tree Zigzag Level Order Traversal ↗ Medium #103
• Binary Tree Right Side View ↗ Medium #199
• Average of Levels in Binary Tree ↗ Easy #637

Interview Tips

Key trade-offs to discuss

• Time vs. space trade-offs between approaches
• Handling edge cases (empty inputs, single elements, duplicates)
• Optimization opportunities and when they matter
• Follow-up variations and constraint changes

← Previous
#101 Symmetric Tree Next
#103 Binary Tree Zigzag Level Order Traversal →