Binary Tree Traversal

BSTTranversal.swift

let inOrder = [1, 2, 3, 4, 5, 6, 7, 8, 9]

func createBST(inOrder: [Int]) -> TreeNode? {
    return helper(inOrder, start: 0, end: inOrder.count-1)
}

func helper(arr: [Int], start: Int, end: Int) -> TreeNode? {
    if start > end {
        return nil
    }
    let mid = (start + end) / 2
    let node = TreeNode(arr[mid])
    
    node.left = helper(arr, start: start, end: mid-1)
    node.right = helper(arr, start: mid+1, end: end)
    
    return node
}

let bst = createBST(inOrder)

func printBST(root: TreeNode?) {
    if root != nil {
        printBST(root?.left)
        print(root!.value)
        printBST(root?.right)
    }
}

func printBSTInOrder(root: TreeNode?) {
    var res = [Int]()
    var stk = [TreeNode?]()
    stk.append(root)
    while !stk.isEmpty {
        let top = stk[stk.count-1]
        if top?.left != nil {
            stk.append(top?.left)
            top?.left = nil
        } else {
            res.append(top!.value)
            stk.removeLast()
            if top?.right != nil {
                stk.append(top?.right)
            }
        }
    }
    print(res)
}

func printBSTInOrder2(root: TreeNode?) {
    var res = [Int]()
    var stk = [TreeNode?]()
    
    var p = root
    while !stk.isEmpty || p != nil {
        if p != nil {
            stk.append(p)
            p = p!.left
        } else {
            let node = stk.removeLast()
            res.append(node!.value)
            p = node!.right
        }
    }
    print(res)
}

func printBSTPreOrder(root: TreeNode?) {
    var res = [Int]()
    var stk = [TreeNode?]()
    stk.append(root)
    
    while !stk.isEmpty {
        let p = stk.removeLast()
        res.append(p!.value)
        
        if p!.right != nil {
            stk.append(p?.right)
        }
        
        if p!.left != nil {
            stk.append(p?.left)
        }
    }
    
    print(res)
}

func printBSTPostOrder(root: TreeNode?) {
    var res = [Int]()
    var stk = [TreeNode?]()
    stk.append(root)
    
    var prev:TreeNode? = nil
    
    while !stk.isEmpty {
        let curr = stk[stk.count-1]!
        
        if prev == nil || prev?.left === curr || prev?.right === curr {
            if curr.left != nil {
                stk.append(curr.left)
            } else if curr.right != nil {
                stk.append(curr.right)
            } else {
                stk.removeLast()
                res.append(curr.value)
            }
            
        } else if (curr.left === prev) {
            if curr.right != nil {
                stk.append(curr.right)
            } else {
                stk.removeLast()
                res.append(curr.value)
            }
        } else if (curr.right === prev) {
            stk.removeLast()
            res.append(curr.value)
        }
        
        prev = curr
    }
    
    print(res)
}