Binary Tree Level Order Traversal
Binary Tree Level Order Traversal
Given the root of a binary tree, return its level order traversal as a nested list. Each sublist should contain the node values at a specific level, ordered from left to right.
Example 1:
Illustration :
Input: root = [1,2,3,4,5,6,7]
Output: [[1],[2,3],[4,5,6,7]]
Output: [[1],[2,3],[4,5,6,7]]
Example 2:
- Input: root = [1]
- Output: [[1]]
Example 3:
- Input: root = [ ]
- Output: [ ]
Constraints:
- 0 <= Number of nodes in both trees <= 1000.
- -1000 <= Node.val <= 1000
Hints to Solve Binary Tree Level Order Traversal
Recommendation for Time and Space Complexity:
Aim for a solution with O(n) time and O(n) space, where n is the total number of nodes in the tree.
Hint 1 :
Level of a tree consists of all nodes at the same distance from the root. Can you think of a way to traverse the tree level by level instead of diving deeper?
Hint 2 :
Use the Breadth First Search (BFS) algorithm to traverse the tree level by level. BFS relies on a queue, where at each step, nodes are processed, and their left and right children are added to the queue. This ensures all levels are explored sequentially.
Hint 3 :
Number of queue iterations equals the number of levels in the tree. For each level, process all nodes currently in the queue and add their values to the result. This way, nodes from each level are grouped together.
There are mainly 2 approach to solve this problem:
- Depth First Search Method (DFS)
- Breadth First Search Method (BFS)
1. Depth First Search Method
Use recursion to traverse the tree depth-wise while keeping track of the current level. Add node values to the corresponding level in the result list as you visit each node.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* 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> res;
vector> levelOrder(TreeNode* root) {
dfs(root, 0);
return res;
}
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (res.size() == depth) {
res.push_back(vector());
}
res[depth].push_back(node->val);
dfs(node->left, depth + 1);
dfs(node->right, depth + 1);
}
};
Java
/**
* 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;
* }
* }
*/
public class Solution {
List> res = new ArrayList<>();
public List> levelOrder(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode node, int depth) {
if (node == null) {
return;
}
if (res.size() == depth) {
res.add(new ArrayList<>());
}
res.get(depth).add(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
}
Python
# 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]]:
res = []
def dfs(node, depth):
if not node:
return None
if len(res) == depth:
res.append([])
res[depth].append(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
return res
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @return {number[][]}
*/
levelOrder(root) {
let res = [];
/**
* @param {TreeNode} node
* @param {number} depth
*/
function dfs(node, depth) {
if (!node) return;
if (res.length === depth) {
res.push([]);
}
res[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
dfs(root, 0);
return res;
}
}
2. Breadth First Search Method
Traverse the tree level by level using a queue. Process all nodes at the current level, add their values to the result list, and enqueue their children for the next level.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* 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> levelOrder(TreeNode* root) {
vector> res;
if (!root) return res;
queue q;
q.push(root);
while (!q.empty()) {
vector level;
int size = q.size();
for (int i = q.size(); i > 0; i--) {
TreeNode* node = q.front();
q.pop();
if (node) {
level.push_back(node->val);
q.push(node->left);
q.push(node->right);
}
}
if (!level.empty()) {
res.push_back(level);
}
}
return res;
}
};
Java
/**
* 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> levelOrder(TreeNode root) {
List> res = new ArrayList<>();
Queue q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
List level = new ArrayList<>();
for (int i = q.size(); i > 0; i--) {
TreeNode node = q.poll();
if (node != null) {
level.add(node.val);
q.add(node.left);
q.add(node.right);
}
}
if (level.size() > 0) {
res.add(level);
}
}
return res;
}
}
Python
# 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]]:
res = []
q = collections.deque()
q.append(root)
while q:
qLen = len(q)
level = []
for i in range(qLen):
node = q.popleft()
if node:
level.append(node.val)
q.append(node.left)
q.append(node.right)
if level:
res.append(level)
return res
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @return {number[][]}
*/
levelOrder(root) {
let res = [];
if (!root) return res;
const q = new Queue();
q.push(root);
while (!q.isEmpty()) {
let level = [];
for (let i = q.size(); i > 0; i--) {
let node = q.pop();
if (node !== null) {
level.push(node.val);
q.push(node.left);
q.push(node.right);
}
}
if (level.length > 0) {
res.push(level);
}
}
return res;
}
}
