Lowest Common Ancestor

LowestCommonAncestor.swift

class TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ value: Int) {
        self.value = value
    }
}

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    if root == nil || root === p || root === q {
        return root
    }

    let leftLCA = lowestCommonAncestor(root?.left, p, q)
    let rightLCA = lowestCommonAncestor(root?.right, p, q)
    print(leftLCA?.value)
    print(rightLCA?.value)

    if leftLCA != nil && rightLCA != nil {
        return root
    } else if leftLCA != nil {
        return leftLCA
    } else {
        return rightLCA
    }
}

// Example usage:
let root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left?.left = TreeNode(6)
root.left?.right = TreeNode(2)
root.right?.left = TreeNode(0)
root.right?.right = TreeNode(8)
root.left?.right?.left = TreeNode(7)
root.left?.right?.right = TreeNode(4)

let p = root.left?.left // Node with value 5
let q = root.left?.right?.right // Node with value 1

let lca = lowestCommonAncestor(root, p, q)
print("Lowest Common Ancestor: \(lca?.value ?? -1)") // Output: Lowest Common Ancestor: 3