Swift BST Sequences answer

BST_Sequences.swift

//
//  main.swift
//  BST_Sequences
//
//  Created by Bill, Yiu Por Chan on 12/20/23.
//

import Foundation

class Node {
    let val:Int
    let left: Node?
    let right: Node?

    init(val: Int, left: Node? = nil, right: Node? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }

    var isLeaf: Bool {
        return left == nil && right == nil
    }
}

let tree = Node(val: 4, 
                left: Node(val:2,
                           left: Node(val: 1),
                           right: Node(val: 3)),
                right: Node(val:5))

func sequence(treeNode: Node, isRoot: Bool = false) -> [[Int]] {
    let result: [Int] = [treeNode.val]

    if treeNode.isLeaf {
        return [result]
    }

    var lefts = [[Int]]()
    if let left = treeNode.left {
        lefts = sequence(treeNode: left)
    }

    var rights = [[Int]]()
    if let right = treeNode.right {
        rights = sequence(treeNode: right)
    }


    var weaved = [[Int]]()
    rights.forEach() { r in
        lefts.forEach() { l in
            weave(first: r, second: l, prefix: [], results: &weaved)
        }
    }

    for i in 0..<weaved.count {
        weaved[i] = result + weaved[i]
    }
    return weaved
}

func weave(first: [Int], second: [Int], prefix: [Int], results: inout [[Int]]) {
    var result = [Int]()
    if first.isEmpty || second.isEmpty {
        result = prefix + first + second
        results.append(result)
        return
    }

    var firstClone = first
    var prefixClone = prefix

    if !firstClone.isEmpty {
        prefixClone.append(firstClone.removeFirst())
    }

    weave(first: firstClone, second: second, prefix: prefixClone, results: &results)

    var secondClone = second
    prefixClone = prefix

    if !secondClone.isEmpty {
        prefixClone.append(secondClone.removeFirst())
    }

    weave(first: first, second: secondClone, prefix: prefixClone, results: &results)
}

let result = sequence(treeNode: tree, isRoot: true)
print(result)