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 simple family tree where each person has a number representing their age. You want to find out if there is a path from the oldest ancestor (root) down to any youngest family member (leaf) where the sum of ages equals a specific number.

🎯 Goal: You will build a small program in C that creates a binary tree with exact ages, sets a target sum, checks if any root-to-leaf path sums to that target, and prints the result.

📋 What You'll Learn

Create a binary tree with nodes having exact integer values

Set an integer variable for the target sum

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

Print 1 if such a path exists, otherwise 0

💡 Why This Matters

🌍 Real World

Checking path sums in trees is useful in decision-making systems, network routing, and game development where paths represent sequences of choices or states.

💼 Career

Understanding tree traversal and recursion is fundamental for software engineers working with hierarchical data, algorithms, and system design.

1

Create the binary tree nodes

Create a struct called TreeNode with int val, TreeNode *left, and TreeNode *right. Then create nodes with these exact values and connections:
root with value 5,
root->left with value 4,
root->right with value 8,
root->left->left with value 11,
root->right->left with value 13,
root->right->right with value 4,
root->left->left->left with value 7,
root->left->left->right with value 2,
root->right->right->right with value 1.

DSA C

// Define struct TreeNode and create the tree nodes with exact values and connections
// Your code here

Hint

Start by defining the TreeNode struct and a helper function newNode to create nodes. Then build the tree by linking nodes exactly as described.

2

Set the target sum

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

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(8);
    root->left->left = newNode(11);
    root->right->left = newNode(13);
    root->right->right = newNode(4);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(2);
    root->right->right->right = newNode(1);
    
    // Create an integer variable called targetSum and set it to 22
    // Your code here
    return 0;
}

Hint

Just add a line inside main to create int targetSum = 22;.

3

Write the path sum checking function

Write a function called hasPathSum that takes TreeNode *root and int sum as parameters and returns int. It should return 1 if there is a root-to-leaf path where the sum of node values equals sum, otherwise 0. Use recursion and check if root is NULL, if leaf node, and recursively check left and right subtrees with updated sum.

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Write the function hasPathSum(TreeNode *root, int sum) here
// Your code here

int main() {
    TreeNode* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(8);
    root->left->left = newNode(11);
    root->right->left = newNode(13);
    root->right->right = newNode(4);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(2);
    root->right->right->right = newNode(1);
    
    int targetSum = 22;
    
    // Your code here
    return 0;
}

Hint

Use recursion to check if the current node is NULL (return 0), if leaf node check if value equals sum, else subtract current node value from sum and check left and right subtrees.

4

Print the result of path sum check

Call hasPathSum with root and targetSum inside main and print the returned integer (1 or 0) using printf.

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int hasPathSum(TreeNode *root, int sum) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return (root->val == sum) ? 1 : 0;
    }
    int newSum = sum - root->val;
    return hasPathSum(root->left, newSum) || hasPathSum(root->right, newSum);
}

int main() {
    TreeNode* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(8);
    root->left->left = newNode(11);
    root->right->left = newNode(13);
    root->right->right = newNode(4);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(2);
    root->right->right->right = newNode(1);
    
    int targetSum = 22;
    
    // Call hasPathSum and print the result
    // Your code here
    return 0;
}

Hint

Call hasPathSum(root, targetSum) and print the result using printf("%d\n", ...).

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 binary tree

D. The sum of all node values in the binary 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

   This is different from finding max depth, counting leaves, or summing all nodes. It specifically checks for a path with a certain sum.

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 means root-to-leaf sum check [OK]

Hint: Look for root-to-leaf path sums, not total or max values [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not root-to-leaf
• Counting nodes instead of summing values

2. Which of the following is the correct C function signature to check if a binary tree has a root-to-leaf path with a given sum?

easy

A. int hasPathSum(struct TreeNode* root, int sum);

B. void hasPathSum(struct TreeNode* root, int sum);

C. int hasPathSum(int root, int sum);

D. bool hasPathSum(struct TreeNode* root);

Solution

1. Step 1: Identify correct parameter types

   The function needs the root pointer of the tree (struct TreeNode*) and the target sum (int).

2. Step 2: Identify correct return type

   The function returns an int (usually 0 or 1) indicating false or true for path existence.

3. Final Answer:

   int hasPathSum(struct TreeNode* root, int sum); -> Option A

4. Quick Check:

   Function returns int and takes root pointer and sum [OK]

Hint: Function returns int and takes root pointer plus sum [OK]

Common Mistakes:

• Using void return type instead of int
• Passing root as int instead of pointer
• Missing sum parameter

3. Given the binary tree below and target sum = 22, what will the function hasPathSum return?

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

medium

A. 0

B. 1

C. Error

D. Undefined

Solution

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

   Paths and sums: - 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

   The path 5->4->11->2 sums to 22, so the function returns true (1).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Path sum 22 exists = 1 [OK]

Hint: Check all root-to-leaf sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Stopping at non-leaf nodes
• Miscomputing sums

4. Consider this buggy C code snippet for path sum check:

int hasPathSum(struct TreeNode* root, int sum) {
  if (!root) return 0;
  if (!root->left && !root->right && root->val == sum) return 1;
  return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

What is the bug in this code?

medium

A. It misses subtracting root->val from sum

B. It incorrectly returns 1 for non-leaf nodes

C. It does not handle empty tree correctly

D. It correctly implements the path sum check

Solution

1. Step 1: Analyze base cases

   Returns 0 if root is NULL (empty tree). Returns 1 if leaf node value equals sum.

2. Step 2: Analyze recursive calls

   Recursively checks left and right subtrees with updated sum (sum - root->val).

3. Final Answer:

   It correctly implements the path sum check -> Option D

4. Quick Check:

   Code matches standard path sum logic [OK]

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

Common Mistakes:

• Missing leaf node check
• Not subtracting root value from sum
• Returning wrong values for NULL nodes

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which data structure is best to store the current path during recursion?

hard

A. A queue to process nodes level by level

B. A hash map to store node values and counts

C. A stack or dynamic array to track nodes in current path

D. A linked list to store all leaf nodes

Solution

1. Step 1: Understand path tracking during recursion

   To record the current path from root to current node, a stack or dynamic array is used to push and pop nodes as recursion goes deeper or backtracks.

2. Step 2: Differentiate from other data structures

   A queue is for breadth-first traversal, hash map is for counting, linked list for storing nodes but not efficient for backtracking paths.

3. Final Answer:

   A stack or dynamic array to track nodes in current path -> Option C

4. Quick Check:

   Use stack/array for path tracking [OK]

Hint: Use stack or array to track path during recursion [OK]

Common Mistakes:

• Using queue instead of stack for path tracking
• Not backtracking path correctly
• Using hash map for path storage