C Program: Determine Binary Tree path with parget sum

Last update on December 20 2024 13:09:38 (UTC/GMT +8 hours)

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.