Breadth-First Search

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

Ref: https://en.wikipedia.org/wiki/Breadth-first_search


class Node {
    var left: Node?
    var right: Node?
    var val: Int?
    init(val: Int) {
        self.val = val
    }
}

// Establish tree
//          1
//       2    3
//     4  5  6  7
let n1 = Node(val: 1)
let n2 = Node(val: 2)
let n3 = Node(val: 3)
let n4 = Node(val: 4)
let n5 = Node(val: 5)
let n6 = Node(val: 6)
let n7 = Node(val: 7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

func breadthFirstSearchIterative(root: Node?) {
    guard let root = root else {
        return
    }
    var queue: [Node] = []
    queue.append(root)
    while !queue.isEmpty {
        let n = queue.removeFirst()
        print(n.val!)
        if let right = n.right {
            queue.append(right)
        }
        if let left = n.left {
            queue.append(left)
        }
    }
}

breadthFirstSearchIterative(root: n1)
%d