Solution 1 - Recursive DFS

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. We recursively subtract the current node's value from targetSum and check if we reach a leaf with a remaining sum of zero.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0112.1 - Path Sum - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """Path Sum Function"""
        if not root:
            return False

        targetSum -= root.val
        if not root.left and not root.right:
            return targetSum == 0

        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.right.right = TreeNode(1)
    print(Solution().hasPathSum(root, 22))  # True

    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    print(Solution().hasPathSum(root2, 5))  # False

    print(Solution().hasPathSum(None, 0))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0112.1 - Path Sum - Solution 1 - Recursive DFS */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /** Path Sum Function */
    hasPathSum(root, targetSum) {
        if (!root) return false;

        targetSum -= root.val;
        if (!root.left && !root.right) return targetSum === 0;

        return (
            this.hasPathSum(root.left, targetSum) ||
            this.hasPathSum(root.right, targetSum)
        );
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    const root = new TreeNode(
        5,
        new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
        new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))),
    );
    console.log(new Solution().hasPathSum(root, 22)); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0112.1 - Path Sum - Solution 1 - Recursive DFS */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(
        public val: number = 0,
        public left: TreeNode | null = null,
        public right: TreeNode | null = null,
    ) {}
}

class Solution {
    /** Path Sum Function */
    hasPathSum(root: TreeNode | null, targetSum: number): boolean {
        if (!root) return false;

        targetSum -= root.val;
        if (!root.left && !root.right) return targetSum === 0;

        return this.hasPathSum(root.left, targetSum) || this.hasPathSum(root.right, targetSum);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    const root = new TreeNode(
        5,
        new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
        new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))),
    );
    console.log(new Solution().hasPathSum(root, 22)); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0112.1 - Path Sum - Solution 1 - Recursive DFS

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	targetSum -= root.Val
	if root.Left == nil && root.Right == nil {
		return targetSum == 0
	}

	return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}

func testcase() {
	root := &TreeNode{
		Val: 5,
		Left: &TreeNode{
			Val: 4,
			Left: &TreeNode{
				Val: 11,
				Left: &TreeNode{Val: 7},
				Right: &TreeNode{Val: 2},
			},
		},
		Right: &TreeNode{
			Val: 8,
			Left: &TreeNode{Val: 13},
			Right: &TreeNode{Val: 4, Right: &TreeNode{Val: 1}},
		},
	}
	fmt.Println(hasPathSum(root, 22)) // true
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0112.1 - Path Sum - Solution 1 - Recursive DFS

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn has_path_sum(root: &Option<Box<TreeNode>>, target_sum: i32) -> bool {
    match root {
        None => false,
        Some(node) => {
            let remaining = target_sum - node.val;
            if node.left.is_none() && node.right.is_none() {
                return remaining == 0;
            }
            has_path_sum(&node.left, remaining) || has_path_sum(&node.right, remaining)
        }
    }
}

fn main() {
    println!("{}", has_path_sum(&None, 0));
}

Solution 2 - Iterative DFS (Stack)

Instead of using recursion, we use an explicit stack to perform depth-first traversal. Each entry in the stack stores a node and the remaining sum needed. When we reach a leaf node, we check if the remaining sum equals the leaf's value.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack) """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """Path Sum Function"""
        if not root:
            return False

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

        while stack:
            node, remaining = stack.pop()
            if not node.left and not node.right and remaining == 0:
                return True

            if node.right:
                stack.append((node.right, remaining - node.right.val))
            if node.left:
                stack.append((node.left, remaining - node.left.val))

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.right.right = TreeNode(1)
    print(Solution().hasPathSum(root, 22))  # True

    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    print(Solution().hasPathSum(root2, 5))  # False

    print(Solution().hasPathSum(None, 0))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /** Path Sum Function */
    hasPathSum(root, targetSum) {
        if (!root) return false;

        const stack = [[root, targetSum - root.val]];
        while (stack.length) {
            const [node, remaining] = stack.pop();
            if (!node.left && !node.right && remaining === 0) return true;

            if (node.right) stack.push([node.right, remaining - node.right.val]);
            if (node.left) stack.push([node.left, remaining - node.left.val]);
        }
        return false;
    }
}

function testcase() {
    const root = new TreeNode(1, new TreeNode(2));
    console.log(new Solution().hasPathSum(root, 3)); // true
}

testcase();

/** 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
    constructor(
        public val: number = 0,
        public left: TreeNode | null = null,
        public right: TreeNode | null = null,
    ) {}
}

class Solution {
    /** Path Sum Function */
    hasPathSum(root: TreeNode | null, targetSum: number): boolean {
        if (!root) return false;

        const stack: Array<[TreeNode, number]> = [[root, targetSum - root.val]];
        while (stack.length) {
            const [node, remaining] = stack.pop() as [TreeNode, number];
            if (!node.left && !node.right && remaining === 0) return true;

            if (node.right) stack.push([node.right, remaining - node.right.val]);
            if (node.left) stack.push([node.left, remaining - node.left.val]);
        }
        return false;
    }
}

function testcase(): void {
    const root = new TreeNode(1, new TreeNode(2));
    console.log(new Solution().hasPathSum(root, 3)); // true
}

testcase();

// 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack)

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Pair struct {
	Node      *TreeNode
	Remaining int
}

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func hasPathSumIterative(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	stack := []Pair{{Node: root, Remaining: targetSum - root.Val}}
	for len(stack) > 0 {
		p := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		node := p.Node
		rem := p.Remaining

		if node.Left == nil && node.Right == nil && rem == 0 {
			return true
		}
		if node.Right != nil {
			stack = append(stack, Pair{Node: node.Right, Remaining: rem - node.Right.Val})
		}
		if node.Left != nil {
			stack = append(stack, Pair{Node: node.Left, Remaining: rem - node.Left.Val})
		}
	}
	return false
}

func testcase() {
	root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}}
	fmt.Println(hasPathSumIterative(root, 3)) // true
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack)

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn has_path_sum_iterative(root: Option<Box<TreeNode>>, target_sum: i32) -> bool {
    if root.is_none() {
        return false;
    }

    let mut stack: Vec<(Box<TreeNode>, i32)> = Vec::new();
    let root = root.unwrap();
    stack.push((root, target_sum - root.val));

    while let Some((node, remaining)) = stack.pop() {
        if node.left.is_none() && node.right.is_none() && remaining == 0 {
            return true;
        }
        if let Some(r) = node.right {
            stack.push((r, remaining - r.val));
        }
        if let Some(l) = node.left {
            stack.push((l, remaining - l.val));
        }
    }
    false
}

fn main() {
    println!("{}", has_path_sum_iterative(None, 0));
}

0112 - Path Sum

Solution 1 - Recursive DFS

Solution 2 - Iterative DFS (Stack)