Path Sum Root to Leaf in Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Path Sum Check for a Simple Tree

What is the output of the following Go code that checks if a path sum exists from root to leaf?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == sum
    }
    return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 11}
    root.Left.Left.Left = &TreeNode{Val: 7}
    root.Left.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 13}
    root.Right.Right = &TreeNode{Val: 4}
    root.Right.Right.Right = &TreeNode{Val: 1}
    fmt.Println(hasPathSum(root, 22))
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Trace the path sums from root to leaf nodes and check if any equals 22.

The code checks if there is a root-to-leaf path with sum 22. The path 5->4->11->2 sums to 22, so the output is true.

❓ Predict Output

intermediate

Output of Path Sum Check with No Valid Path

What does the following Go code print when checking for a path sum of 26?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == sum
    }
    return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    fmt.Println(hasPathSum(root, 26))
}

A false

B Compilation error

C true

D Runtime panic

💡 Hint

Check if any root-to-leaf path sums to 26 in this small tree.

The tree has paths 1->2 (sum 3) and 1->3 (sum 4). Neither equals 26, so output is false.

🔧 Debug

advanced

Identify the Error in Path Sum Function

What error does the following Go code produce when run?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == sum
    }
    return hasPathSum(root.Left, sum-root.Val) && hasPathSum(root.Right, sum-root.Val)
}
func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 8}
    fmt.Println(hasPathSum(root, 9))
}

A Runtime panic

B false

C Compilation error

D true

💡 Hint

Check the logical operator used to combine recursive calls.

The code uses && instead of ||, so it requires both left and right paths to sum correctly, which is not correct. The output is false.

🧠 Conceptual

advanced

Number of Root-to-Leaf Paths with Given Sum

Given a binary tree, which approach correctly counts how many root-to-leaf paths sum to a target value?

A Use recursion to explore all paths, increment count when leaf node sum matches target, and sum counts from left and right subtrees.

B Use breadth-first search and stop at first path that matches sum to count paths.

C Return true if any path sum matches target, else false; count is number of true returns.

D Only check sums of left subtree paths and multiply by right subtree sums to get count.

💡 Hint

Think about exploring all paths and accumulating counts.

Counting paths requires exploring all root-to-leaf paths and summing counts where path sums match target. Option A describes this correctly.

🚀 Application

expert

Find All Root-to-Leaf Paths with Given Sum

Which code snippet correctly returns all root-to-leaf paths where the sum of node values equals the target sum?

A

func pathSum(root *TreeNode, sum int) [][]int {
    var res [][]int
    var path []int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, currSum int) {
        if node == nil {
            return
        }
        path = append(path, node.Val)
        currSum += node.Val
        if node.Left == nil && node.Right == nil && currSum == sum {
            temp := make([]int, len(path))
            copy(temp, path)
            res = append(res, temp)
        } else {
            dfs(node.Left, currSum)
            dfs(node.Right, currSum)
        }
        path = path[:len(path)-1]
    }
    dfs(root, 0)
    return res
}

B

func pathSum(root *TreeNode, sum int) [][]int {
    var res [][]int
    var dfs func(*TreeNode, int, []int)
    dfs = func(node *TreeNode, currSum int, path []int) {
        if node == nil {
            return
        }
        currSum += node.Val
        path = append(path, node.Val)
        if node.Left == nil && node.Right == nil && currSum == sum {
            res = append(res, path)
        }
        dfs(node.Left, currSum, path)
        dfs(node.Right, currSum, path)
    }
    dfs(root, 0, []int{})
    return res
}

C

func pathSum(root *TreeNode, sum int) [][]int {
    var res [][]int
    var path []int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, currSum int) {
        if node == nil {
            return
        }
        path = append(path, node.Val)
        currSum += node.Val
        if node.Left == nil && node.Right == nil && currSum == sum {
            res = append(res, path)
        } else {
            dfs(node.Left, currSum)
            dfs(node.Right, currSum)
        }
        path = path[:len(path)-1]
    }
    dfs(root, 0)
    return res
}

D

func pathSum(root *TreeNode, sum int) [][]int {
    var res [][]int
    var dfs func(*TreeNode, int, []int)
    dfs = func(node *TreeNode, currSum int, path []int) {
        if node == nil {
            return
        }
        currSum += node.Val
        path = append(path, node.Val)
        if node.Left == nil && node.Right == nil && currSum == sum {
            temp := make([]int, len(path))
            copy(temp, path)
            res = append(res, temp)
        }
        dfs(node.Left, currSum, path)
        dfs(node.Right, currSum, path)
    }
    dfs(root, 0, []int{})
    return res
}

💡 Hint

Look for correct path copying to avoid shared slices in results.

Option D correctly copies the path slice before appending to results, avoiding shared slice mutation issues. It passes path as a parameter and accumulates sum correctly.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. If there exists a root-to-leaf path with a sum equal to a given target

B. The maximum depth of the binary tree

C. The total number of leaf nodes in the tree

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals a given target sum.

2. Step 2: Differentiate from other tree properties

   It is not about counting leaves, finding max depth, or summing all nodes, but specifically about a path sum from root to leaf.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option A

4. Quick Check:

   Path sum = target? [OK]

Hint: Focus on root-to-leaf paths, not entire tree sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking paths that don't end at leaf nodes
• Ignoring the root node in the sum

2. Which of the following Go function signatures correctly represents a function to check path sum in a binary tree node defined as type TreeNode struct { Val int; Left, Right *TreeNode }?

easy

A. func hasPathSum(root TreeNode, sum int) bool

B. func hasPathSum(root *TreeNode, sum int) bool

C. func hasPathSum(root *TreeNode, sum int) int

D. func hasPathSum(root TreeNode, sum int) int

Solution

1. Step 1: Identify correct parameter types

   The root node should be passed as a pointer to TreeNode to allow nil checks and avoid copying the entire node.

2. Step 2: Identify correct return type

   The function should return a boolean indicating if such a path exists, not an integer.

3. Final Answer:

   func hasPathSum(root *TreeNode, sum int) bool -> Option B

4. Quick Check:

   Pointer param + bool return = correct signature [OK]

Hint: Use pointer receiver and bool return for path existence [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Returning int instead of bool
• Using incorrect parameter order

3. What is the output of the following Go code snippet?

package main

import "fmt"

type TreeNode struct {
  Val int
  Left, Right *TreeNode
}

func hasPathSum(root *TreeNode, sum int) bool {
  if root == nil {
    return false
  }
  if root.Left == nil && root.Right == nil {
    return root.Val == sum
  }
  return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}

func main() {
  root := &TreeNode{5, &TreeNode{4, &TreeNode{11, &TreeNode{7, nil, nil}, &TreeNode{2, nil, nil}}, nil}, &TreeNode{8, &TreeNode{13, nil, nil}, &TreeNode{4, nil, &TreeNode{1, nil, nil}}}}
  fmt.Println(hasPathSum(root, 22))
}

medium

A. Compilation error

B. false

C. Runtime panic

D. true

Solution

1. Step 1: Trace the path sums in the tree

   Check if any root-to-leaf path sums to 22. One path is 5->4->11->2 = 22, so the function returns true.

2. Step 2: Confirm function logic correctness

   The function correctly checks leaf nodes and recursively subtracts node values from sum, returning true if any path matches.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Path 5+4+11+2 = 22 [OK]

Hint: Look for any root-to-leaf path summing to target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Not subtracting node value from sum
• Assuming sum must be at root only

4. The following Go function is intended to check if a path sum exists but has a bug. What is the bug?

func hasPathSum(root *TreeNode, sum int) bool {
  if root == nil {
    return false
  }
  if root.Left == nil && root.Right == nil {
    return sum == root.Val
  }
  return hasPathSum(root.Left, sum-root.Val) && hasPathSum(root.Right, sum-root.Val)
}

medium

A. Using && instead of || causes incorrect results

B. Missing base case for nil root

C. Incorrect comparison order in leaf check

D. Not subtracting root.Val from sum in recursive calls

Solution

1. Step 1: Analyze recursive return condition

   The function uses logical AND (&&) to combine left and right subtree results, which requires both to be true.

2. Step 2: Understand correct logic for path sum

   We want to return true if either left or right subtree has a valid path, so logical OR (||) should be used instead.

3. Final Answer:

   Using && instead of || causes incorrect results -> Option A

4. Quick Check:

   Use OR (||) to find any valid path [OK]

Hint: Use OR (||) to combine subtree results, not AND (&&) [OK]

Common Mistakes:

• Using AND instead of OR in recursive calls
• Forgetting to check leaf nodes properly
• Not handling nil root correctly

5. Given a binary tree where node values can be negative, zero, or positive, which modification is necessary to correctly check for a path sum equal to a target value?

hard

A. Only consider paths with positive sums

B. Stop recursion early if sum becomes negative

C. No modification needed; the standard path sum check works for all values

D. Use breadth-first search instead of depth-first search

Solution

1. Step 1: Understand path sum logic with negative values

   The standard recursive approach subtracts node values from sum and checks leaf nodes; negative values do not break this logic.

2. Step 2: Evaluate unnecessary optimizations

   Stopping early on negative sums or ignoring negative paths can miss valid paths; BFS is not required for correctness.

3. Final Answer:

   No modification needed; the standard path sum check works for all values -> Option C

4. Quick Check:

   Standard DFS works with negatives [OK]

Hint: Standard DFS path sum works regardless of node values sign [OK]

Common Mistakes:

• Stopping recursion on negative sums
• Ignoring negative or zero values in paths
• Switching to BFS unnecessarily