Leetcode 623. Add One Row to Tree

Link to 623

Solution

Let's start with an easier problem: traverse a binary tree with a BFS algorithm.

     func BFSTraverse(_ root: TreeNode) -> () {
        
        //establish a queue
        var queue = [ TreeNode ]()
        
        //queue a starting node
        queue.append(root)
        
        while !queue.isEmpty {
            
            //traverse the next queued node
            guard let bitem = queue.first else {
                break
            }
            print("now traversing item: \(bitem.val)")
            //add descendants to the queue
            if let left = bitem.left {
                queue.append(left)
            }
            if let right = bitem.right {
                queue.append(right)
            }
            queue = Array(queue.dropFirst())
        }
        
        print("bfs traversal complete..")
        
    }

Now if we have the following binary tree:

let root = TreeNode(4)
root.left = TreeNode(2)
root.left!.right = TreeNode(3)
root.left!.left = TreeNode(0)
root.left!.right!.right = TreeNode(1)
let s = Solution()
s.BFSTraverse(root)

We get:

now traversing item: 4
now traversing item: 2
now traversing item: 0
now traversing item: 3
now traversing item: 1
bfs traversal complete..

Now we have to modify the BFS program in order to add nodes when we reach the level depth - 1:

public class Solution {
    
    func addOneRow(_ root: TreeNode?, _ val: Int, _ depth: Int) -> TreeNode? {
        if depth == 1 {
            let n = TreeNode(val)
            n.left = root
            return n
        }
        
        var queue = [TreeNode]()
        queue.append(root!)
        var d = 1
        while d < depth - 1  {
            var temp = [ TreeNode]()
            while  !queue.isEmpty {
                let node: TreeNode = queue.removeFirst()
                if node.left != nil { temp.append(node.left!)}
                if node.right  != nil { temp.append(node.right!) }
            }
            queue = temp
            d += 1
        }
        
        while  !queue.isEmpty {
            let node = queue.removeFirst()
            var temporal = node.left
            
                node.left = TreeNode(val)
                node.left!.left = temporal
        
            temporal = node.right
           
                node.right =  TreeNode(val)
                node.right!.right = temporal
            
            
        }
        return root
        
    }
}