Path Sum Root to Leaf in Binary Tree in DSA C# - Build from Scratch

Path Sum Root to Leaf in Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. Each person has a number representing their age. You want to find if there is a path from the oldest ancestor (root) down to a youngest descendant (leaf) where the sum of ages equals a specific number.

🎯 Goal: Build a program that checks if there is a root-to-leaf path in a binary tree where the sum of node values equals a given target sum.

📋 What You'll Learn

Create a binary tree with exact node values

Create a target sum variable

Write a function to check if a root-to-leaf path sums to the target

Print the result as True or False

💡 Why This Matters

🌍 Real World

Checking paths in trees is useful in decision-making systems, file directory structures, and network routing where conditions must be met along a path.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles, especially those involving data structures, algorithms, and system design.

1

Create the Binary Tree

Create a class called TreeNode with an integer val, and two TreeNode references called left and right. Then create the following tree structure by creating TreeNode objects and linking them:

Root node with val = 5
Left child of root with val = 4
Right child of root with val = 8
Left child of node 4 with val = 11
Left child of node 11 with val = 7
Right child of node 11 with val = 2
Left child of node 8 with val = 13
Right child of node 8 with val = 4
Right child of node 4 (right child of 8) with val = 1

Assign the root node to a variable called root.

DSA C#

// Define TreeNode class and create the tree nodes as described
// Your code here

Hint

Start by defining the TreeNode class with the required fields and constructor. Then create each node and link them carefully as per the instructions.

2

Set the Target Sum

Create an integer variable called targetSum and set it to 22.

DSA C#

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

// Create targetSum variable and set it to 22
// Your code here

Hint

Just create a variable named targetSum and assign it the value 22.

3

Write the Path Sum Function

Write a method called HasPathSum that takes a TreeNode root and an integer sum. It returns true if there is a root-to-leaf path where the sum of node values equals sum, otherwise false. Use recursion to check:
- If root is null, return false.
- If root is a leaf node (no left and right), check if root.val == sum.
- Otherwise, recursively check left and right subtrees with sum - root.val.

DSA C#

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

int targetSum = 22;

// Write HasPathSum method below
// Your code here

Hint

Use recursion to check if the current node is null or a leaf. If leaf, compare value to sum. Otherwise, check left and right children with updated sum.

4

Print the Result

Print the result of calling HasPathSum with root and targetSum. Use Console.WriteLine to print True or False.

DSA C#

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

int targetSum = 22;

bool HasPathSum(TreeNode root, int sum)
{
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == sum;
    return HasPathSum(root.left, sum - root.val) || HasPathSum(root.right, sum - root.val);
}

// Print the result of HasPathSum(root, targetSum)
// Your code here

Hint

Call HasPathSum(root, targetSum) and print the result using Console.WriteLine.

Practice

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

easy

A. The total number of nodes in the binary tree

B. The maximum depth of the binary tree

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

D. The sum of all node values in the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks to check if any path from the root node down to any leaf node sums up exactly to a given target value.

2. Step 2: Identify what is being checked

   We are not asked for maximum depth, total nodes, or sum of all nodes, but specifically for a path sum equal to the target.

3. Final Answer:

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

4. Quick Check:

   Path sum check = If there exists a root-to-leaf path with a sum equal to a given target [OK]

Hint: Look for a path from root to leaf matching target sum [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Looking for maximum depth instead

2. Which of the following C# method signatures correctly represents a function to check path sum in a binary tree node class?

easy

A. public bool HasPathSum(TreeNode root, int targetSum)

B. public int HasPathSum(TreeNode root, int targetSum)

C. public void HasPathSum(TreeNode root, int targetSum)

D. public string HasPathSum(TreeNode root, int targetSum)

Solution

1. Step 1: Determine the return type for path sum check

   The function should return true or false indicating if such a path exists, so return type must be bool.

2. Step 2: Check method signature correctness

   public bool HasPathSum(TreeNode root, int targetSum) returns bool and takes root node and target sum as parameters, matching the problem requirements.

3. Final Answer:

   public bool HasPathSum(TreeNode root, int targetSum) -> Option A

4. Quick Check:

   Return type bool for yes/no check = public bool HasPathSum(TreeNode root, int targetSum) [OK]

Hint: Return bool for yes/no path sum check [OK]

Common Mistakes:

• Using int or void return type instead of bool
• Returning string instead of boolean
• Incorrect parameter types or order

3. Given the following binary tree and targetSum = 22, what will the method HasPathSum(root, 22) return?

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

medium

A. Runtime error

B. true

C. null

D. false

Solution

1. Step 1: Identify root-to-leaf paths and their sums

   Check paths: 5->4->11->7 = 27, 5->4->11->2 = 22, 5->8->13 = 26, 5->8->4->1 = 18.

2. Step 2: Check if any path sum equals 22

   Path 5->4->11->2 sums to 22, so the method returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Path sum 22 exists = true [OK]

Hint: Sum each root-to-leaf path to find target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Summing partial paths not ending at leaf
• Miscomputing sums of nodes

4. The following C# code attempts to check path sum but has a bug. What is the error?

public bool HasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);
}

medium

A. No bug; code works correctly

B. Should check for null root after subtracting value

C. Incorrect base case for leaf node check

D. Missing return statement in recursive calls

Solution

1. Step 1: Analyze base cases and recursion

   Code returns false if root is null, correctly handles leaf node by comparing value to targetSum, and recursively checks left and right subtrees with updated targetSum.

2. Step 2: Confirm correctness of logic

   All conditions and recursive calls are correct and return statements are present.

3. Final Answer:

   No bug; code works correctly -> Option A

4. Quick Check:

   Code logic matches problem requirements = No bug; code works correctly [OK]

Hint: Check base cases and recursive returns carefully [OK]

Common Mistakes:

• Forgetting to subtract node value from targetSum
• Missing return keyword in recursion
• Incorrect leaf node condition

5. You want to find all root-to-leaf paths in a binary tree where the sum of node values equals a target sum. Which approach best extends the path sum check to collect all such paths?

hard

A. Sum all nodes and compare to target sum once traversal ends

B. Use BFS and stop at first path matching the sum

C. Use recursion without tracking path, just return true/false

D. Use DFS with a list to track current path and add to result when sum matches at leaf

Solution

1. Step 1: Understand the requirement to collect all paths

   We need to find all root-to-leaf paths with sum equal to target, so we must track the current path during traversal.

2. Step 2: Choose the correct traversal and tracking method

   DFS with a list to store nodes along the current path allows backtracking and collecting all valid paths when leaf and sum conditions are met.

3. Final Answer:

   Use DFS with a list to track current path and add to result when sum matches at leaf -> Option D

4. Quick Check:

   Track paths with DFS and list = Use DFS with a list to track current path and add to result when sum matches at leaf [OK]

Hint: Track path nodes during DFS to collect all valid paths [OK]

Common Mistakes:

• Using BFS which is less natural for path tracking
• Not tracking path nodes, only sums
• Stopping at first found path instead of all