Solving Binary Tree Level Order Traversal

Marhaba 👋🏼

Welcome to another article on solving programming problems in Swift. I’ll be covering the Binary Tree Level Order Traversal problem.

Yalla, let’s begin.

Table of Contents

1. Problem Statement

2. Problem Analysis

3. Solution

Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

  Input: root = []
  Output: []

Here’s the initial code below without a solution.

  
/**
 * 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]] {
    	/// Implementation here
	}
}
  

Problem Analysis

Without thinking about code, let’s envision a level-order traversal step by step starting with the root node.

Level 1:

First, we start with the root node whose value is 10. So we track that in values.

Next, we see the root node has children 14 (left) and 24 (right). So let’s track that in children.

Level 2:

Now we start with child 14. As we did prior, let’s add 14 to values. Now let’s add its children (1, 30) to children.

Sweet, we’ll move on with 24 and do the same. Add it to values and add its child (11) to children.

Level 3:

We're at the final level. Since all nodes at level 3 have no children, we’ll just add each node value to values from left to right.

Did you notice a pattern? Let’s notate some observations from our analysis:

• We started with root, collecting its value and children in values and children

• To proceed to the next level, we iterate through all children in a first-in, first-out sequence. As with root, we update values and children.

• We continue until all levels are exhausted.

Based on our knowledge of data structures and algorithms we know:

1. A Queue data structure is required

2. Iterating via level-by-level resembles a breadth-first search algorithm.

Now that we have everything we need to implement our solution, let’s code!

Solution

First, I’ll cover an edge case for when the root node is nil, which will return an empty list. Assuming our root node is not nil, then I’ll proceed with initializing a queue with the root node and a multi-dimensional array with the root node value.

Remember, queue will track child nodes while finalElements will track values at each level.

  
	func levelOrder(_ root: TreeNode?) -> [[Int]] {
		guard let root = root else {
            return []
		}

		var queue: [TreeNode] = [root]
		var finalElements: [[Int]] = [[root.val]]
        /// More to come...
	}
        
  

Next, I’ll set up the following:

1. A while loop, which will terminate when the queue is empty.

2. Create a tempQueue, which is a copy of the current queue

3. Clear our current queue (you’ll see why in a second)

4. Initialize an empty elements array, which will track values at each level

  
	while !queue.isEmpty {
		var tempQueue: [TreeNode] = queue
		queue = []
            
		var elements: [Int] = []
	}
  

Next, I’ll create an inner while loop that will:

1. Traverse through all nodes in tempQueue using first-in-first-out order.

2. If node has a left child and/or a right child, then:

   • Add its value to elements

   • Add child node to original queue

3. Once all nodes of tempQueue are exhausted (level traversal completion), then we add collected values to finalElements

  
	while !tempQueue.isEmpty {
		let node = tempQueue.removeFirst()
		if let left = node.left {
			elements.append(left.val)
			queue.append(left)
		}

		if let right = node.right {
			elements.append(right.val)
			queue.append(right)
		}
	}
	
    if !elements.isEmpty {
		finalElements.append(elements)
	}
  

Looking good so far. Our last step is returning finalElements. Here’s the full solution below:

  
	func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }

        var queue: [TreeNode] = [root]
        var finalElements: [[Int]] = [[root.val]]
        var queueNextCount = 1

        while !queue.isEmpty {
            var tempQueue: [TreeNode] = queue
            queue = []
            
            var elements: [Int] = []
            while !tempQueue.isEmpty {
                let node = tempQueue.removeFirst()
                if let left = node.left {
                    elements.append(left.val)
                    queue.append(left)
                }

                if let right = node.right {
                    elements.append(right.val)
                    queue.append(right)
                }
            }

            if !elements.isEmpty {
                finalElements.append(elements)
            }
        }

        return finalElements
    }
  

Results

Time Complexity: O(n)

LeetCode Performance:

Stellar runtime and decent memory performance 👏🏼

For any comments and questions on this post, follow up on Twitter.

Make sure to share this article. Appreciate you reading through my blog and until next time.