Binary Tree Level Order Traversal
MedPrompt
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]Example 2:
Input: root = [1]
Output: [[1]]Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a recursive helper function, which is a form of Depth-First Search (DFS), to traverse the tree. We pass the current node and its level as arguments to the function. The level number is used to determine which sublist in our result list the node's value should be added to.
Algorithm
- Initialize an empty list of lists,
result. - Define a helper function
dfs(node, level, result). - In the main function, call
dfs(root, 0, result)if the root is not null. - Inside
dfs:- If
nodeis null, return. - If
levelequalsresult.size(), it means we're visiting this level for the first time. Add a new empty list toresult. - Get the list for the current
levelfromresultand addnode.valto it. - Recursively call
dfsfor the left child withlevel + 1. - Recursively call
dfsfor the right child withlevel + 1.
- If
- Return
result.
Walkthrough
The core idea is to perform a preorder traversal (visiting the node, then its left child, then its right child) while keeping track of the current depth or level. We use a list of lists to store the result. When we visit a node at a certain level, we check if a list for that level already exists in our result list. If the level is equal to the current size of the result list, it means we are visiting this level for the first time, so we create a new list for it. Then, we add the node's value to the list corresponding to its level. The process is then repeated recursively for the left and right children at level + 1.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } dfs(root, 0, result); return result; } private void dfs(TreeNode node, int level, List<List<Integer>> result) { if (node == null) { return; } // If this is the first time we are visiting this level, create a new list. if (level == result.size()) { result.add(new ArrayList<Integer>()); } // Add the current node's value to the list for its level. result.get(level).add(node.val); // Recur for the left and right children. dfs(node.left, level + 1, result); dfs(node.right, level + 1, result); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
The code can be very concise and is straightforward if one is comfortable with recursion.
Cons
It is not a natural way to solve a level-order problem, as DFS explores depth-wise.
For very deep trees, this approach can lead to a
StackOverflowErrordue to deep recursion.
This is the classic and most intuitive approach for level order traversal. It uses a queue data structure to process nodes in a breadth-first manner. We process the tree one level at a time, adding all nodes from a single level to the queue, and then processing them to find the nodes of the next level.
Algorithm
- Initialize an empty list of lists,
result. - If
rootis null, return the emptyresult. - Initialize a queue (e.g.,
LinkedList) and add therootto it. - Start a
whileloop that runs as long as the queue is not empty.- Inside the loop, get the current size of the queue,
levelSize. - Create a new list,
currentLevel, to store the values of the nodes at the current level. - Loop
levelSizetimes:- Dequeue a node from the queue.
- Add the node's value to
currentLevel. - If the node's left child is not null, enqueue it.
- If the node's right child is not null, enqueue it.
- After the inner loop, add
currentLeveltoresult.
- Inside the loop, get the current size of the queue,
- Return
result.
Walkthrough
We start by initializing a queue and adding the root node to it. The main logic is a while loop that continues as long as the queue is not empty. Inside this loop, we first determine the number of nodes at the current level by checking the queue's size. We then iterate that many times, dequeuing one node at a time, adding its value to a temporary list for the current level, and enqueuing its non-null children. After the inner loop finishes processing all nodes of the current level, the temporary list containing their values is added to our final result list. This process guarantees that we traverse the tree level by level from left to right.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currentNode = queue.poll(); currentLevel.add(currentNode.val); if (currentNode.left != null) { queue.offer(currentNode.left); } if (currentNode.right != null) { queue.offer(currentNode.right); } } result.add(currentLevel); } return result; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
This is the canonical and most intuitive solution for this problem.
Being iterative, it avoids the risk of stack overflow for very deep trees.
It naturally processes the tree level by level, matching the problem's requirement.
Cons
May use slightly more memory than a DFS approach on a very narrow and deep (skewed) tree, although both have the same worst-case complexity.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < List < Integer >> levelOrder ( TreeNode root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } ans . add ( t ); } return ans ; } }/** * Definition for a binary tree node. * 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 levelOrder = function (root) { let ans = []; if (!root) { return ans; } let q = [root]; while (q.length) { let t = []; for (let n = q.length; n; --n) { const { val, left, right } = q.shift(); t.push(val); left && q.push(left); right && q.push(right); } ans.push(t); } return ans; };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> levelOrder ( TreeNode * root ) { vector < vector < int >> ans ; if ( ! root ) return ans ; queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . push_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans . push_back ( t ); } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def levelOrder ( self , root : Optional [ TreeNode ]) -> List [ List [ int ]]: ans = [] if root is None : return ans q = deque ([ root ]) while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.