Binary Tree Level Order Traversal (Leetcode 102)

Difficulty : Medium Link: Day 12: May Leetcode Challenge

Problem Description

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).

Examples

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

Constraints

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

Solution

Recursive

The first approach could to start recursively since its intuitive. We can pass another parameter for level and further incrementing it by every call, thus marking the change of levels. This approach would of course we slow and for every new level we will have to iterate older levels every time.

Breadth-First Search

A BFS approach involves the use of a data structure called Queue(q) so that we deal with the nodes of the tree in the proper order. The queue operates in a First In First Out (FIFO) order, so insertions would be at the end and removing from the front. We can use that property and we can calculate the number of items to be processed in the next level by finding the count of elements in the queue after every iteration.

Swift

class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return []}
var queue = [TreeNode]()
var output = [[Int]]()
queue.append(root)
while queue.isEmpty == false {
// start new level
// number of elements in the current level
var levelCount = queue.count
var levelNodes = [Int]()
while levelCount > 0 {
let node = queue.first!
queue.removeFirst()
levelCount -= 1
levelNodes.append(node.val)
// Add Left child node
if let left = node.left{
queue.append(left)
}
// Add right child node
if let right = node.right{
queue.append(right)
}
}
// Add nodes by level
output.append(levelNodes)
}
return output
}
}

Python

from collections import deque
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
levels = []
if not root:
return levels
level = 0
queue = deque([root,])
while queue:
# start the current level
levels.append([])
# number of elements in the current level
level_length = len(queue)
for i in range(level_length):
node = queue.popleft()
# fulfill the current level
levels[level].append(node.val)
# add child nodes of the current level
# in the queue for the next level
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# go to next level
level += 1
return levels

Java

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
if (root == null) return levels;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int level = 0;
while ( !queue.isEmpty() ) {
// start the current level
levels.add(new ArrayList<Integer>());
// number of elements in the current level
int level_length = queue.size();
for(int i = 0; i < level_length; ++i) {
TreeNode node = queue.remove();
// fulfill the current level
levels.get(level).add(node.val);
// add child nodes of the current level
// in the queue for the next level
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
// go to next level
level++;
}
return levels;
}
}

Complexity Analysis

  • Time complexity = O(N) since each node is processed exactly once.
  • Space complexity = O(N) to keep the output structure which contains N node values

Leave a Reply

Your email address will not be published. Required fields are marked *