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 value 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 exists a root-to-leaf path in a binary tree such that the sum of the node values along the path equals a given target sum.

📋 What You'll Learn

Create a binary tree node structure with integer values

Build a sample 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 path sums in trees is useful in decision trees, network routing, and financial modeling where paths represent sequences of choices or transactions.

💼 Career

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

1

Create the Binary Tree Node Structure and Build the Tree

Define a struct called TreeNode with an integer val, and two pointers left and right. Then create the following binary tree exactly: root node with value 5, left child 4, right child 8, left child of 4 is 11, left and right children of 11 are 7 and 2, right child of 8 is 4, and right child of this 4 is 1.

DSA C++

// Define TreeNode struct and create the binary tree as described
// Your code here

Hint

Start by defining the TreeNode struct with a constructor. Then create each node and link them exactly as described.

2

Create the Target Sum Variable

Inside main(), create an integer variable called targetSum and set it to 22.

DSA C++

#include 
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int main() {
    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->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);
    
    // Create an integer variable called targetSum and set it to 22
    // Your code here
    return 0;
}

Hint

Simply declare int targetSum = 22; inside main().

3

Write the Function to Check Path Sum

Write a function called hasPathSum that takes a TreeNode* called 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 and check if the current node is null, if it is a leaf, and subtract the node's value from sum as you go down.

DSA C++

#include 
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Write the hasPathSum function here
// Your code here

int main() {
    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->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);
    
    int targetSum = 22;
    return 0;
}

Hint

Use recursion to check if the current node is null, then if it's a leaf check if sum == root->val. Otherwise, subtract root->val from sum and check left and right subtrees.

4

Print the Result of Path Sum Check

In main(), call hasPathSum(root, targetSum) and print true if it returns true, otherwise print false.

DSA C++

#include 
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool hasPathSum(TreeNode* root, int sum) {
    if (root == nullptr) {
        return false;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return sum == root->val;
    }
    int remainingSum = sum - root->val;
    return hasPathSum(root->left, remainingSum) || hasPathSum(root->right, remainingSum);
}

int main() {
    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->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);
    
    int targetSum = 22;
    
    // Print true if hasPathSum(root, targetSum) is true, else print false
    // Your code here
    return 0;
}

Hint

Call hasPathSum(root, targetSum) and print true if it returns true, else print false.