Solution For Binary Tree Level Order Traversal
The problem statement is as follows:
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).
Approach:
The problem can be easily solved using BFS. We can traverse the tree level by level and store the nodes on each level in a list. We can then add the list to a final result list which contains the level order traversal of the tree.
Algorithm:
Create an empty queue and add the root node to it.
While the queue is not empty, repeat steps 3 to 5.
Dequeue a node from the queue and add its value to the current level list.
Enqueue the left and right child of the dequeued node if they exist.
If the current level has been fully traversed, add the current level list to the final result list, and reset the current level list to an empty list.
Return the final result list.
Code:
“`
from collections import deque
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque()
queue.append(root)
while queue:
current_level = []
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
“`
Time Complexity:
The time complexity of the above algorithm is O(N) where N is the number of nodes in the binary tree. We visit each node only once in the worst case.
Space Complexity:
The space complexity of the above algorithm is O(N) where N is the number of nodes in the binary tree. In the worst case, when the tree is a complete binary tree, the maximum size of the queue would be (N/2)+1. Therefore, the space complexity of the algorithm is also O(N).
Step by Step Implementation For Binary Tree Level Order Traversal
/**
* 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) {
// we will use a queue to keep track of the nodes at each level
Queue queue = new LinkedList<>();
List> result = new ArrayList<>();
// if the root is null, return an empty list
if (root == null) {
return result;
}
// add the root to the queue
queue.add(root);
// while the queue is not empty
while (!queue.isEmpty()) {
// create a list to store the nodes at the current level
List level = new ArrayList<>();
// calculate the number of nodes at the current level
int size = queue.size();
// for each node at the current level
for (int i = 0; i < size; i++) {
// remove the node from the queue
TreeNode node = queue.remove();
// add the node's value to the list
level.add(node.val);
// if the node has a left child, add it to the queue
if (node.left != null) {
queue.add(node.left);
}
// if the node has a right child, add it to the queue
if (node.right != null) {
queue.add(node.right);
}
}
// add the list of nodes at the current level to the result
result.add(level);
}
// return the result
return result;
}
} from collections import deque
# 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: TreeNode) -> List[List[int]]:
# Base case
if not root:
return []
# Initialize a queue and result list
queue = deque([root])
result = []
# Loop while queue is not empty
while queue:
# Get the size of the queue
queue_size = len(queue)
# Initialize a list to store the current level
current_level = []
# Loop through the queue
for _ in range(queue_size):
# Pop the first node from the queue
node = queue.popleft()
# Add the node's value to the current level list
current_level.append(node.val)
# Add the node's children (if any) to the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Add the current level list to the result
result.append(current_level)
# Return the result
return result/**
* 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) {
// edge case - if root is null, return empty array
if (!root) {
return [];
}
// create an array to store the final result
const result = [];
// create an array to store nodes at each level
const nodes = [root];
// while there are nodes in the array
while (nodes.length > 0) {
// create an array to store values at each level
const values = [];
// iterate through nodes
for (let i = 0; i < nodes.length; i++) {
// add node value to the array
values.push(nodes[i].val);
// if node has a left child, add it to the array
if (nodes[i].left) {
nodes.push(nodes[i].left);
}
// if node has a right child, add it to the array
if (nodes[i].right) {
nodes.push(nodes[i].right);
}
}
// remove the nodes we just visited from the array
nodes.splice(0, nodes.length);
// add the values array to the result
result.push(values);
}
// return the result
return result;
};/**
* 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) {
// Base case
if (root == nullptr) {
return {};
}
// Result vector
vector> result;
// Queue for BFS
queue q;
q.push(root);
// Perform BFS
while (!q.empty()) {
// Get the size of the current level
int levelSize = q.size();
// Vector for the current level
vector level;
// Process all nodes of the current level
for (int i = 0; i < levelSize; i++) {
// Dequeue a node from the queue
TreeNode* currNode = q.front();
q.pop();
// Add the node's value to the current level
level.push_back(currNode->val);
// Enqueue the node's children (if any)
if (currNode->left != nullptr) {
q.push(currNode->left);
}
if (currNode->right != nullptr) {
q.push(currNode->right);
}
}
// Add the current level to the result
result.push_back(level);
}
return result;
}
}; /**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public IList> LevelOrder(TreeNode root) {
// Base case
if (root == null)
{
return new List>();
}
// BFS
Queue queue = new Queue();
List> result = new List>();
queue.Enqueue(root);
while (queue.Count != 0)
{
// Get the size of the current level
int levelSize = queue.Count;
List currentLevel = new List();
for (int i = 0; i < levelSize; i++)
{
TreeNode currentNode = queue.Dequeue();
currentLevel.Add(currentNode.val);
// Add the child nodes of the current node to the queue
if (currentNode.left != null)
{
queue.Enqueue(currentNode.left);
}
if (currentNode.right != null)
{
queue.Enqueue(currentNode.right);
}
}
// Add the current level to the result
result.Add(currentLevel);
}
return result;
}
}