C Program: Determine Binary Tree path with parget sum

C Program to implement Tree Structure: Exercise-9 with Solution

Write a C program to determine if a binary tree has a root-to-leaf path whose sum equals a given target sum.

Sample Solution:

C Code:

// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new node
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

// Function to check if a path with the given sum exists in the binary tree
bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL) {
        return false;
    }

    // Check if the current node is a leaf
    if (root->left == NULL && root->right == NULL) {
        return (targetSum - root->data) == 0;
    }

    // Recursively check the left and right subtrees
    bool leftPath = hasPathSum(root->left, targetSum - root->data);
    bool rightPath = hasPathSum(root->right, targetSum - root->data);

    return leftPath || rightPath;
}

// Function to free the memory allocated for the binary tree
void freeTree(struct TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    // Build a sample binary tree
    struct TreeNode* root = createNode(5);
    root->left = createNode(4);
    root->right = createNode(8);
    root->left->left = createNode(11);
    root->left->left->left = createNode(7);
    root->left->left->right = createNode(2);
    root->right->left = createNode(13);
    root->right->right = createNode(4);
    root->right->right->right = createNode(1);

    // Set the target sum
    int targetSum = 18;
    // Check if a path with the given sum exists
    if (hasPathSum(root, targetSum)) {
        printf("Path with sum %d exists in the binary tree.\n", targetSum);
    } else {
        printf("No path with sum %d exists in the binary tree.\n", targetSum);
    }

    // Free allocated memory
    freeTree(root);

    return 0;
}

Output:

Path with sum 18 exists in the binary tree.

Explanation:

In the exercise above,

• Structure Definition:
• struct TreeNode: Represents a binary tree node with integer data and pointers to left and right children.
• Node Creation Function:
• createNode: Allocates memory for a new node, initializes its data, and sets left and right pointers to 'NULL'.
• Path Sum Checking Function:
• hasPathSum: Checks if there is a path from the root to any leaf node in the binary tree such that the sum of node values along the path equals the given 'targetSum'.
• Recursively explores the left and right subtrees.
• Tree Traversal and Sum Comparison:
• The main function builds a sample binary tree.
• Sets a targetSum variable.
• Calls hasPathSum to check if a path with the specified sum exists.
• Prints a message indicating whether such a path exists or not.
• Memory Deallocation Function:
• freeTree: Frees the memory allocated for the binary tree nodes.
• Sample Binary Tree in Main:
• Constructs a binary tree with integer values.
• Sets a target sum.
• Checks if there is a path in the tree with a sum equal to the target sum.

Flowchart:

C Programming Code Editor:

Previous: C Program: Expression Tree from Postfix Expression and Evaluation.
Next: Implementing AVL Tree in C: Insertion and Deletion Operations.