NUHMAN.com

Introduction

LeetCode 112: Path Sum asks us to determine whether a given binary tree has a root-to-leaf path that sums to a specific target value. In this problem, we start from the root node and traverse down the tree, checking if there is any path from the root to a leaf node that results in the sum equal to the target value.

A leaf node is defined as a node that has no children (both left and right children are null).

Problem Statement

Given a binary tree and a target sum, return true if there is a path from the root to any leaf node such that the sum of the node values along the path equals the target sum. Otherwise, return false.

Example:

go

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22
Output: true
Explanation: The path 5 -> 4 -> 11 -> 2 sums to 22.
go

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

Approach:

Using Depth-First Search (DFS)

In this problem, we can use Depth-First Search (DFS) to explore each path from the root to the leaf nodes.

1. DFS Algorithm:

• Starting from the root, subtract the node's value from the target sum and recurse to the left and right subtrees.
• If we reach a leaf node and the target sum becomes 0, return true as we found a valid path.
• If we reach a null node or a leaf node with a target sum not equal to 0, return false.
• The key observation is that if the current node’s value matches the remaining target sum, we continue checking both left and right subtrees for a valid path.

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
}

// hasPathSum uses DFS to check if there is a path with the given sum.
func hasPathSum(root *TreeNode, sum int) bool {
    // If the root is nil, there is no path.
    if root == nil {
        return false
    }

    // Subtract the current node's value from the target sum.
    sum -= root.Val

    // If we reach a leaf node and the sum is zero, return true.
    if root.Left == nil && root.Right == nil {
        return sum == 0
    }

    // Recursively check the left and right subtrees.
    return hasPathSum(root.Left, sum) || hasPathSum(root.Right, sum)
}

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. hasPathSum Function:

• This function uses DFS to check if there is a path with the given sum in the tree.
• First, we check if the root node is nil. If it is, there is no path, so we return false.
• We then subtract the current node's value from the target sum and check if we have reached a leaf node (both left and right children are nil).
• If we are at a leaf node and the sum is 0, we return true, indicating we found a valid path.
• If we are not at a leaf node, we recursively check the left and right subtrees with the updated target sum.

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), where h is the height of the tree. This is due to the recursion stack during the DFS traversal. 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).

Edge Cases

1. Empty Tree:

• Input: root = nil, target = 5
• Output: false
• Explanation: An empty tree has no paths, so it can't have any path sum.

1. Single Node Tree:

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

1. Target Sum Not Reached:

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

1. Multiple Valid Paths:

• Input: root = [1, 2, 3], target = 3
• Output: true
• Explanation: The path 1 -> 2 sums to 3, so it should return true.

Conclusion

LeetCode 112: Path Sum is a problem that tests your understanding of binary tree traversal. By utilizing DFS, we can efficiently find the path in the binary tree that sums to a given target value. This 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.