Binary Tree Level Order Traversal

                                            
/**
 * 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>> result;
        if (root == nullptr) {
            return result;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            
            for (int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                level.push_back(curr->val);
                
                if (curr->left) {
                    q.push(curr->left);
                }
                if (curr->right) {
                    q.push(curr->right);
                }
            }
            
            result.push_back(level);
        }
        
        return result;
    }
};

                                            
/**
 * 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> levelValues = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                levelValues.add(currentNode.val);
                
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            
            result.add(levelValues);
        }
        
        return result;
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            level_values = []
            
            for _ in range(level_size):
                node = queue.pop(0)
                level_values.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level_values)
        
        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)
 * }
 */

var levelOrder = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    
    const result: number[][] = [];
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const currentLevelVals: number[] = [];
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node) {
                currentLevelVals.push(node.val);
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
        }
        
        result.push(currentLevelVals);
    }
    
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        
        var result: [[Int]] = []
        var queue: [TreeNode] = [root]
        
        while !queue.isEmpty {
            var currentLevelValues: [Int] = []
            for _ in 0..<queue.count {
                let node = queue.removeFirst()
                currentLevelValues.append(node.val)
                if let left = node.left { queue.append(left) }
                if let right = node.right { queue.append(right) }
            }
            result.append(currentLevelValues)
        }
        
        return result
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }
    
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        level := []int{}
        nextLevelNodes := []*TreeNode{}
        
        for _, node := range queue {
            level = append(level, node.Val)
            if node.Left != nil {
                nextLevelNodes = append(nextLevelNodes, node.Left)
            }
            if node.Right != nil {
                nextLevelNodes = append(nextLevelNodes, node.Right)
            }
        }
        
        result = append(result, level)
        queue = nextLevelNodes
    }
    
    return result
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
# end

def level_order(root)
    return [] if root.nil?
    
    result = []
    queue = [root]
    
    until queue.empty?
        level = []
        size = queue.size
        
        size.times do
            node = queue.shift
            level << node.val
            
            queue << node.left if node.left
            queue << node.right if node.right
        end
        
        result << level
    end
    
    result
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null)
 */

object Solution {
    def levelOrder(root: TreeNode): List[List[Int]] = {
        import scala.collection.mutable.Queue
        var result = List[List[Int]]()
        if (root == null) return result
        val queue = Queue[TreeNode](root)
        while (queue.nonEmpty) {
            val currLevel = queue.dequeueAll(_ => true)
            val levelValues = currLevel.map(_.value)
            result = result :+ levelValues.toList
            for (node <- currLevel) {
                if (node.left != null) queue.enqueue(node.left)
                if (node.right != null) queue.enqueue(node.right)
            }
        }
        result
    }
}

                                            
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }

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

impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        
        if let Some(node) = root {
            let mut queue = std::collections::VecDeque::new();
            queue.push_back(node);
            
            while !queue.is_empty() {
                let mut level_values = Vec::new();
                let level_size = queue.len();
                
                for _ in 0..level_size {
                    if let Some(curr) = queue.pop_front() {
                        let curr_node = curr.borrow();
                        level_values.push(curr_node.val);
                        
                        if let Some(left) = &curr_node.left {
                            queue.push_back(left.clone());
                        }
                        
                        if let Some(right) = &curr_node.right {
                            queue.push_back(right.clone());
                        }
                    }
                }
                
                result.push(level_values);
            }
        }
        
        result
    }
}

To solve this coding challenge, we need to perform a level order traversal of a binary tree. Level order traversal means we visit the tree level by level from left to right, starting from the root, then proceeding to the next level, and so on. We will use a queue to help us perform this Breadth-First Search (BFS) traversal efficiently. Given the constraints, we also need to ensure our solution can handle up to 2000 nodes and node values ranging from -1000 to 1000.

Explanation

Understanding the Problem : Given a binary tree, we need to return the values of nodes in a level order traversal. This means we will return a list of lists, where each inner list contains the values of nodes at a specific level, starting from the root, then moving to the next level, and so on.
Breadth-First Search (BFS) : The BFS technique is optimal for traversing the binary tree level by level. Here, we use a queue to keep track of nodes at each level. By dequeuing a node and enqueuing its children, we can effectively traverse each level completely before moving on to the next.
Queue Usage : Initialize the queue with the root node. For each node, after processing its value, enqueue its left and right children if they exist. Continue this process until the queue is empty.
Edge Cases : Handle the edge case of an empty tree (i.e., when the root is
null

or
None

) by returning an empty list immediately.
Returning the Result : Collect the node values at each level in a temporary list and append this list to the result list at the end of each level's processing. Finally, return the result list.

Let's now break down the solution into detailed pseudocode.

Detailed Steps in Pseudocode

Initialization :

Check if the root is null. If it is, return an empty list.
Initialize an empty list
result

to store the final level order traversal.
Initialize a queue with the root node as the only initial element.

                                            
# Check if the root node is null
IF root IS null
RETURN []

# Initialize the result list to store level order traversal
result = []

# Initialize the queue with the root node
queue = [root]

Level-order Traversal Using Queue :

While the queue is not empty:

Determine the number of nodes at the current level (i.e., the length of the queue).
Initialize an empty list
level_values

to store the values of the current level's nodes.
For each node at the current level:

Dequeue the node from the front of the queue.
Add the node's value to
level_values

.
If the left child of the node is not null, enqueue it.
If the right child of the node is not null, enqueue it.

After processing all nodes at the current level, append
level_values

to
result

.

                                            
# Process nodes level by level
WHILE queue IS NOT EMPTY
# Number of nodes at the current level
level_size = LENGTH(queue)

# List to store node values of the current level
level_values = []

# Process each node at the current level
FOR i FROM 1 TO level_size
# Remove the node from the queue
node = DEQUEUE(queue)

# Add the node's value to the current level's list
level_values.APPEND(node.value)

# Add the left child to the queue if it exists
IF node.left IS NOT null
QUEUE.APPEND(node.left)

# Add the right child to the queue if it exists
IF node.right IS NOT null
QUEUE.APPEND(node.right)

# Append the current level's values to the result list
result.APPEND(level_values)

Return the Result :

After processing all levels, return the
result

list.

                                            
# Return the final level order traversal
RETURN result

The above detailed explanation and pseudocode provide a clear methodology to solve the binary tree level order traversal problem using the BFS technique with the help of a queue. This approach ensures that we gracefully handle all edge cases and conform to the problem's constraints.