Swift Coding Test Course, Finding the Least Common Ancestor 2

Hello! Today, we will tackle the problem of finding the Lowest Common Ancestor (LCA) in Swift coding tests for those preparing for it. This problem involves finding the closest common ancestor of two nodes in a tree structure and has various applications. It is also one of the frequently appearing problems in coding tests.

Problem Description

When given a binary tree with two nodes, write a function to find the lowest common ancestor of these two nodes. The nodes of the binary tree are defined as follows:

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
            self.left = nil
            self.right = nil
        }
    }

For example, consider the following binary tree:

The lowest common ancestor of node 5 and node 1 is node 3. In the case of node 5 and node 4, the lowest common ancestor is node 5.

Input Format

The function is defined in the following format:

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode?

Here, root is the root node of the binary tree, and p and q represent the respective nodes. These nodes exist in the tree.

Solution Process

There are various approaches to solve this problem, but one of the most efficient methods is to use recursion. Below, I will explain the process of solving the problem using this method step-by-step.

Step 1: Basic Idea

Through tree traversal, we can consider the following three cases for each node:

If the current node matches p or q
If we are searching for p or q in the left subtree
If we are searching for p or q in the right subtree

Through these cases, we can deduce the lowest common ancestor. If we find one node in each of the two subtrees, the current node is the lowest common ancestor.

Step 2: Implementing the Recursive Function

Now, we implement a recursive function to find the two nodes at each node:

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        // If the node to check is nil
        guard let current = root else { return nil }

        // If the current node is p or q
        if current === p || current === q {
            return current
        }

        // Search for the respective nodes in the left and right subtrees
        let left = lowestCommonAncestor(current.left, p, q)
        let right = lowestCommonAncestor(current.right, p, q)

        // If we found one in both the left and right subtrees
        if left != nil && right != nil {
            return current
        }

        // If we found one only in one subtree
        return left ?? right
    }

In the code above, we check whether the current node is nil using the guard let statement and test whether the current node matches p or q. After that, we recursively call the function on the left and right subtrees and store the results in left and right. If we find results in both subtrees, we return the current node as the lowest common ancestor.

Step 3: Writing Test Cases

Now, we will add some test cases to test the function we wrote:

    let root = TreeNode(value: 3)
    let node5 = TreeNode(value: 5)
    let node1 = TreeNode(value: 1)
    let node6 = TreeNode(value: 6)
    let node2 = TreeNode(value: 2)
    let node0 = TreeNode(value: 0)
    let node8 = TreeNode(value: 8)
    let node7 = TreeNode(value: 7)
    let node4 = TreeNode(value: 4)

    // Connecting the tree structure
    root.left = node5
    root.right = node1
    node5.left = node6
    node5.right = node2
    node1.left = node0
    node1.right = node8
    node2.left = node7
    node2.right = node4

    // Testing
    let lca1 = lowestCommonAncestor(root, node5, node1) // Result should be 3
    let lca2 = lowestCommonAncestor(root, node5, node4) // Result should be 5

We execute the test cases to check the results. In this case, we validate whether the expected results come out and whether each node’s lowest common ancestor is found correctly.

Time Complexity Analysis

The time complexity of this algorithm is O(N). This is because, in the worst case, we may need to traverse all nodes; thus, it takes up to O(N) time for a tree with N nodes. Additionally, the space complexity is O(H), where H represents the depth of the tree. This refers to the depth of the recursive call stack.

Conclusion

Today, we learned how to solve the problem of finding the lowest common ancestor in a binary tree using Swift. This problem frequently appears in coding tests, so it is important to develop the skill to solve problems quickly when they arise. By utilizing a recursive approach to solve the problem, we improved the efficiency of the code and emphasized the understanding. I will return with another interesting algorithmic problem next time!