Swift DSA: Binary Tree Level Order Traversal

Swift: Binary Tree Level Order Traversal

Problem: Binary Tree Level Order Traversal

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]]
Explanation:
    3
   / \
  9  20
     / \
    15  7

Input: root = [1]
Output: [[1]]

Input: root = []
Output: []

Swift Solution

// Definition for a binary tree node
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    // Basic Level Order Traversal
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        
        var result = [[Int]]()
        var queue = [(root, 0)]
        var currentLevel = 0
        var currentLevelValues = [Int]()
        
        while !queue.isEmpty {
            let (node, level) = queue.removeFirst()
            
            // If we've moved to a new level, add the previous level's values
            if level > currentLevel {
                result.append(currentLevelValues)
                currentLevelValues = []
                currentLevel = level
            }
            
            currentLevelValues.append(node.val)
            
            // Add children to queue with their level
            if let left = node.left {
                queue.append((left, level + 1))
            }
            if let right = node.right {
                queue.append((right, level + 1))
            }
        }
        
        // Add the last level
        if !currentLevelValues.isEmpty {
            result.append(currentLevelValues)
        }
        
        return result
    }
    
    // Alternative implementation with more features
    func advancedLevelOrder(_ root: TreeNode?) -> LevelOrderResult {
        guard let root = root else { return LevelOrderResult(values: [], depths: [:], width: 0, height: 0) }
        
        var result = [[Int]]()
        var nodeDepths = [Int: Int]()  // Map node values to their depths
        var maxWidth = 0
        var currentLevel = 0
        var queue = [(root, 0)]
        var currentLevelNodes = 0
        
        while !queue.isEmpty {
            let levelSize = queue.count
            var levelValues = [Int]()
            currentLevelNodes = 0
            
            // Process entire level
            for _ in 0..
        
Explanation
        
Basic Algorithm (levelOrder):
        
The solution uses a Breadth-First Search (BFS) approach with these key steps:
        
1. Use a queue to store nodes and their levels
        
2. Process nodes level by level
        
3. Keep track of the current level to group nodes correctly
        
4. Add children to the queue with their level information
        
Advanced Algorithm (advancedLevelOrder):
        
This version includes additional features:
        
- Tracks the depth of each node
        
- Calculates the maximum width of the tree
        
- Determines the height of the tree
        
Time Complexity: O(n) where n is the number of nodes
        
Space Complexity: O(w) where w is the maximum width of the tree
        
Key Techniques Used:
        
1. Queue-based BFS traversal
        
2. Level tracking with tuples
        
3. Batch processing of levels
        
4. Tree metrics calculation
        
Common Variations:
        
1. Zigzag level order traversal
        
2. Bottom-up level order traversal
        
3. Average of levels in binary tree
        
4. Right side view of binary tree
    

• Whatsapp
• Tweet
• Share
• Share
• Share
• Share

Sign up here with your email