Leetcode – Path Sum in Python

Introduction

In computer science, tree traversal is a foundational concept and is widely used in various applications. The Path Sum problem on LeetCode is an excellent example that tests a candidate’s knowledge and skills in tree traversal algorithms, particularly in a binary tree. In this comprehensive article, we will explore the problem in-depth, understand its intricacies, and examine different solutions in Python.

Understanding the Problem

The Path Sum problem asks to determine if the tree has a root-to-leaf path such that adding up all the values along the path equals a given target sum.

For example, consider the following binary tree:

5
/ \
4   8
/   / \
11  13  4
/ \       \
7   2       1

The target sum is 22. There is a path 5 -> 4 -> 11 -> 2, which adds up to 22. So, the answer would be True.

Binary Tree Data Structure

A binary tree is made up of nodes, where each node contains a left reference, a right reference, and a data element. The topmost node is the root of the tree. Here’s how we can define a TreeNode in Python:

class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right

Approach 1: Recursive Depth-First Search (DFS)

One of the common ways to solve the Path Sum problem is by using a depth-first search (DFS). In DFS, we traverse the tree in depth by exploring as far as possible along each branch before backtracking.

Let’s take a look at the Python code for this approach:

class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right

def hasPathSum(root, targetSum):
if not root:
return False

# If this is a leaf node, check if the path sum equals the target sum.
if not root.left and not root.right:
return targetSum == root.value

# Recursively check the left and right sub-trees.
return (hasPathSum(root.left, targetSum - root.value) or
hasPathSum(root.right, targetSum - root.value))

This approach has a time complexity of O(N) where N is the number of nodes, as it visits each node once.

Approach 2: Iterative Depth-First Search (DFS)

An alternative to the recursive DFS is the iterative DFS using a stack. This can sometimes be more efficient in terms of memory usage.

Here is the Python code that uses an iterative DFS approach:

def hasPathSum(root, targetSum):
if not root:
return False

stack = [(root, targetSum - root.value)]

while stack:
node, curr_sum = stack.pop()

# If this is a leaf node, check if the path sum equals the target sum.
if not node.left and not node.right and curr_sum == 0:
return True

if node.right:
stack.append((node.right, curr_sum - node.right.value))
if node.left:
stack.append((node.left, curr_sum - node.left.value))

return False

This approach also has a time complexity of O(N).

Breadth-First Search can also be used to solve this problem. In BFS, we traverse the tree level by level. This approach is particularly useful if you expect the target path to be located on upper levels and want to find it without searching the entire tree.

Here’s how you might implement this approach in Python:

from collections import deque

def hasPathSum(root, targetSum):
if not root:
return False

queue = deque([(root, targetSum - root.value)])

while queue:
node, curr_sum = queue.popleft()

# If this is a leaf node, check if the path sum equals the target sum.
if not node.left and not node.right and curr_sum == 0:
return True

if node.left:
queue.append((node.left, curr_sum - node.left.value))
if node.right:
queue.append((node.right, curr_sum - node.right.value))

return False

This approach has the same time complexity as the DFS approaches, O(N), but may perform better in certain cases based on the structure of the tree.

Understanding Edge Cases and Optimizations

It is important to consider various edge cases such as handling of negative numbers, and extremely skewed trees (which might cause a deep recursive stack).

Conclusion

The Path Sum problem is a classic binary tree problem that tests one’s knowledge in tree traversal algorithms. We discussed three different approaches: recursive DFS, iterative DFS, and BFS. Understanding the problem, choosing the appropriate data structure, and traversal algorithm is crucial. Practice is key in mastering these concepts, so it is highly recommended to solve a variety of tree-based problems.