Swift Coding Test Course, Depth First Search

Problem Description

We want to calculate the sum of all paths in a given binary tree. Each path is from the root to a leaf node. The binary tree is given in the following form:

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

            init(_ val: Int) {
                self.val = val
                self.left = nil
                self.right = nil
            }
        }
        

Here, each node has a value (val) and is connected to a left child (left) and a right child (right). If the following binary tree is given:

               1
              / \
             2   3
            / \
           4   5
        

The sum of the paths from the root node 1 to the leaf nodes 4 and 5 is 7 (1+2+4) and 8 (1+2+5), so the final answer will be 15.

Approach to the Problem

We will use the DFS algorithm to solve this problem. DFS works by starting from a specific node, exploring as deeply as possible, and returning when no further nodes can be reached. In this case, we will calculate the cumulative sum of each path and record that sum when we reach a leaf node.

The steps to solve the problem are as follows:

1. Start from the root node and perform DFS.
2. Add the value (val) of the current node to the cumulative sum.
3. If the current node is a leaf node, add the cumulative sum to the result.
4. If it is not a leaf node, proceed to the left child and the right child, recursively calling DFS.
5. Repeat the above process for all paths to calculate the cumulative sum.

Swift Code Implementation

Now let’s implement the above algorithm in code using Swift.

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

            init(_ val: Int) {
                self.val = val
                self.left = nil
                self.right = nil
            }
        }

        class Solution {
            func sumNumbers(_ root: TreeNode?) -> Int {
                return dfs(root, 0)
            }

            private func dfs(_ node: TreeNode?, _ currentSum: Int) -> Int {
                guard let node = node else { return 0 }
                let newSum = currentSum * 10 + node.val

                if node.left == nil && node.right == nil {
                    return newSum
                }

                return dfs(node.left, newSum) + dfs(node.right, newSum)
            }
        }
        

The above code recursively performs DFS to calculate the sum of the paths. The sumNumbers function takes the root node as an argument, while the dfs function takes the current node and cumulative sum as arguments and returns the final sum. The process is as follows:

1. When the sumNumbers function is called, DFS starts with a current cumulative sum of 0.
2. For each node, the current sum is multiplied by 10 and the node value is added to create a new sum.
3. When a leaf node is reached, that sum is returned, and after adding the sums of the left and right children, the final result is returned.

Test Cases

Let’s create a few test cases to verify that the code works correctly. Here are examples of various binary tree structures.

        let root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left!.left = TreeNode(4)
        root.left!.right = TreeNode(5)

        let solution = Solution()
        print(solution.sumNumbers(root)) // Output: 15
        

In the above test case, we calculate the sum of all paths starting from 1, passing through 2, and reaching 4 and 5. As a result, the sum of 1-2-4 and 1-2-5 adds up to 15.

Performance and Optimization

This problem has a time complexity of O(N) using the DFS method, where N is the number of nodes. The space complexity is O(H), where H is the height of the tree. Since DFS uses a stack, in the worst case, we may need to visit all nodes, resulting in memory usage proportional to the height.

Alternatively, we could use the BFS (Breadth-First Search) method to solve the problem, but for this specific problem of calculating the sum of paths to leaf nodes, DFS is more intuitive and efficient.

Conclusion

In this lecture, we addressed the problem of calculating the path sum to leaf nodes in a binary tree using depth-first search. We understood the concept of the DFS algorithm and implemented it in Swift. Such problems frequently appear in many coding tests, so we encourage you to practice more with various variations of the problem.

Now that we have covered basic DFS, challenge yourself with more complex problems. For example, consider exploring graph traversal, finding connected components, or shortest path problems. We hope you develop more proficient coding skills through practice.