Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Ref: https://en.wikipedia.org/wiki/Depth-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 depthFirstSearch(root: Node?) {
    if root != nil {
        print(root?.val ?? "")
        depthFirstSearch(root: root?.left)
        depthFirstSearch(root: root?.right)
    }
}
depthFirstSearch(root: n1)


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

depthFirstSearchIterative(root: n1)