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.