NUHMAN.com

Introduction

LeetCode 113: Path Sum II asks us to find all root-to-leaf paths in a binary tree where the sum of the node values along the path equals a given target sum. This is an extension of the Path Sum problem, but in this case, instead of returning a boolean result, we are required to return a list of all paths that satisfy the condition.

Problem Statement

Given a binary tree and a target sum, return all root-to-leaf paths where each path’s sum equals the target sum. A leaf node is defined as a node that has no children.

Example:

go

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22
Output: [
    [5,4,11,2],
    [5,8,4,1]
]
go

Input: root = [1,2,3], target = 5
Output: []

Approach:

Using Depth-First Search (DFS)

In this problem, we can use Depth-First Search (DFS) to explore all possible paths from the root to the leaf nodes. We will keep track of the current path and the remaining sum as we traverse down the tree.

1. DFS Algorithm:

• Starting from the root node, subtract the node's value from the target sum and move to the left and right subtrees.
• If we reach a leaf node and the remaining sum is zero, we add the current path to the result.
• If we reach a null node or a leaf node with a remaining sum that is not zero, we backtrack and continue exploring other paths.
• At each recursive step, we add the current node's value to the current path and remove it once we backtrack.

Go Implementation

Solution Using DFS

go

package main

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// pathSum finds all root-to-leaf paths in the binary tree where the sum equals the target sum.
func pathSum(root *TreeNode, sum int) [][]int {
    var result [][]int
    var currentPath []int
    dfs(root, sum, currentPath, &result)
    return result
}

// dfs is a helper function that performs DFS on the binary tree to find the paths.
func dfs(node *TreeNode, sum int, currentPath []int, result *[][]int) {
    if node == nil {
        return
    }

    // Add the current node's value to the path.
    currentPath = append(currentPath, node.Val)

    // If it's a leaf node and the sum matches, add the current path to the result.
    if node.Left == nil && node.Right == nil && sum == node.Val {
        *result = append(*result, append([]int(nil), currentPath...))
    } else {
        // Recurse on the left and right child.
        dfs(node.Left, sum-node.Val, currentPath, result)
        dfs(node.Right, sum-node.Val, currentPath, result)
    }

    // Backtrack by removing the current node from the path.
    currentPath = currentPath[:len(currentPath)-1]
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree. It contains an integer value (Val) and pointers to its left and right children (Left and Right).

1. pathSum Function:

• This function is the main entry point that initializes an empty result and calls the dfs helper function to start the depth-first search.
• It returns a 2D slice ([][]int) where each row represents a valid path.

1. dfs Function:

• The dfs function is a recursive helper that performs depth-first search on the binary tree.
• It first checks if the current node is nil, in which case it returns without doing anything.
• It then appends the current node's value to the currentPath slice.
• If a leaf node is reached and the remaining sum equals the node's value, we add the current path to the result.
• Otherwise, it continues to recursively search the left and right subtrees, adjusting the remaining sum by subtracting the node's value.
• Finally, it backtracks by removing the last element from the currentPath.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the tree.

Time Complexity:

• The time complexity is O(n) because we visit each node in the binary tree exactly once during the DFS traversal.

Space Complexity:

• The space complexity is O(h) due to the recursion stack used in DFS. In the worst case, the height of the tree could be n (if the tree is unbalanced), and in the best case, the height is log n (if the tree is balanced).
• Additionally, the space complexity also includes the space required to store all valid paths, which could be up to O(n) in the worst case if all paths are valid.

Edge Cases

1. Empty Tree:

• Input: root = nil, target = 5
• Output: []
• Explanation: An empty tree has no paths, so no valid paths exist.

1. Single Node Tree:

• Input: root = [1], target = 1
• Output: [[1]]
• Explanation: A single node tree with a target sum equal to the node’s value will return the path [1].

1. Target Sum Not Reached:

• Input: root = [5, 4, 8], target = 20
• Output: []
• Explanation: There is no path in the tree that sums to 20.

1. Multiple Valid Paths:

• Input: root = [1, 2, 3], target = 3
• Output: [[1, 2]]
• Explanation: The path 1 -> 2 sums to 3, so it is included in the result.

Conclusion

LeetCode 113: Path Sum II is an interesting problem that extends the basic path sum problem by requiring us to return all paths that sum to the target value. By using DFS and backtracking, we can efficiently explore all paths in the binary tree and store the valid ones. The solution has O(n) time complexity and O(h) space complexity, where n is the number of nodes, and h is the height of the tree.