Root to leaf path sum equal to a given number in BST

0 0 7 minutes read

Given a BST and a number. The task is to check whether the given number is equal to the sum of all the node from root leaf across any of the root to leaf paths in the given Binary Search Tree.

Approach: The idea is to traverse from root to all leaves in top-down fashion maintaining a path[] array to store current root to leaf path. While traversing, store data of all nodes of current path in the array path[]. Whenever a leaf node is reached, calculate the sum of all of the nodes on the current path using the array path[] and check if it is equal to the given sum.

Below is the implementation of above approach:

C++

// CPP program to check if root to leaf path
// sum to a given number in BST
 
#include<bits/stdc++.h>
using namespace std;
 
// BST node
struct Node { 
    int data; 
    Node *left, *right; 
};
 
/* Helper function that allocates a new node */
Node* newNode(int data) 
{ 
    Node* node = (Node*)malloc(sizeof(Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 
 
// Function to check if root to leaf path
// sum to a given number in BST
int checkThesum(struct Node *root, int path[], int i, int sum)
{
    int sum1 = 0, x, y, j;
     
    if(root == NULL)
        return 0;
         
    // insert the data of a node
    path[i] = root->data;
     
    // if the node is leaf
    // add all the element in array
    if(root->left==NULL&&root->right==NULL)
    {
        for(j = 0; j <= i; j++)
            sum1 = sum1 + path[j];
             
        // if the sum of root node to leaf 
        // node data is equal then return 1
        if(sum == sum1)
            return 1;
        else
            return 0;
    }
 
    x = checkThesum(root->left, path, i+1, sum);
     
    // if x is 1, it means the given sum is matched 
    // with root to leaf node sum
    if(x==1) 
        return 1;
    else
    {
        return checkThesum(root->right, path, i+1, sum);
    }
}
 
// Driver code
int main()
{
    int path[100], sum = 164;
     
    Node *root = newNode(45);
    root->left = newNode(38);
    root->left->left = newNode(33);
    root->left->left->left = newNode(31);
    root->left->left->right = newNode(35);
    root->left->right = newNode(41);
    root->left->right->left = newNode(40);
    root->left->right->right = newNode(44);
    root->right = newNode(50);
    root->right->left = newNode(47);
    root->right->left->left = newNode(46);
    root->right->left->right = newNode(48);
    root->right->right = newNode(52);
    root->right->right->left = newNode(51);
    root->right->right->right = newNode(55);
     
    if(checkThesum(root, path, 0, sum)==1)
        cout<<"YES\n";
    else
        cout<<"NO\n";
         
    return 0;
} 

Java

// Java program to check if 
// root to leaf path sum to
// a given number in BST
class GFG
{
     
// BST node
static class Node 
{ 
    int data; 
    Node left, right; 
}
 
/* Helper function that 
   allocates a new node */
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if root 
// to leaf path sum to a
// given number in BST
static int checkThesum(Node root, int path[],
                           int i, int sum)
{
    int sum1 = 0, x, y, j;
     
    if(root == null)
        return 0;
         
    // insert the data of a node
    path[i] = root.data;
     
    // if the node is leaf
    // add all the element in array
    if(root.left == null && 
       root.right == null)
    {
        for(j = 0; j <= i; j++)
            sum1 = sum1 + path[j];
             
        // if the sum of root node to leaf 
        // node data is equal then return 1
        if(sum == sum1)
            return 1;
        else
            return 0;
    }
 
    x = checkThesum(root.left, path, 
                        i + 1, sum);
     
    // if x is 1, it means the 
    // given sum is matched with 
    // root to leaf node sum
    if(x == 1) 
        return 1;
    else
    {
        return checkThesum(root.right, path,
                                i + 1, sum);
    }
}
 
// Driver code
public static void main(String args[])
{
    int path[] = new int[100], sum = 164;
     
    Node root = newNode(45);
    root.left = newNode(38);
    root.left.left = newNode(33);
    root.left.left.left = newNode(31);
    root.left.left.right = newNode(35);
    root.left.right = newNode(41);
    root.left.right.left = newNode(40);
    root.left.right.right = newNode(44);
    root.right = newNode(50);
    root.right.left = newNode(47);
    root.right.left.left = newNode(46);
    root.right.left.right = newNode(48);
    root.right.right = newNode(52);
    root.right.right.left = newNode(51);
    root.right.right.right = newNode(55);
     
    if(checkThesum(root, path, 0, sum) == 1)
        System.out.print("YES\n");
    else
        System.out.print("NO\n");
} 
}
 
// This code is contributed by Arnab Kundu 

Python3

# Python program to check if root to leaf path
# sum to a given number in BST
import math
 
# BST node
class Node: 
    def __init__(self,data): 
        self.data = data 
        self.left = None
        self.right= None
 
# Helper function that allocates a new node */
def newNode(data): 
    node = Node(data) 
    node.data = data 
    node.left = None
    node.right = None
 
    return node 
 
# Function to check if root to leaf path
# sum to a given number in BST
def checkThesum(root, path, i, sum):
    sum1 = 0
     
    # x, y, j 
    if(root == None):
        return 0
         
    # insert the data of a node
    path[i] = root.data
     
    # if the node is leaf
    # add all the element in array
    if(root.left == None and root.right == None):
        for j in range(0, i + 1):
            sum1 = sum1 + path[j]
             
        # if the sum of root node to leaf 
        # node data is equal then return 1
        if(sum == sum1):
            return 1
        else:
            return 0
     
    x = checkThesum(root.left, path, i + 1, sum)
     
    # if x is 1, it means the given sum is matched 
    # with root to leaf node sum
    if(x == 1):
        return 1
    else:
        return checkThesum(root.right, path, i + 1, sum)
     
# Driver code
if __name__=='__main__': 
 
    path = [None] * 100
    sum = 164
     
    root = newNode(45)
    root.left = newNode(38)
    root.left.left = newNode(33)
    root.left.left.left = newNode(31)
    root.left.left.right = newNode(35)
    root.left.right = newNode(41)
    root.left.right.left = newNode(40)
    root.left.right.right = newNode(44)
    root.right = newNode(50)
    root.right.left = newNode(47)
    root.right.left.left = newNode(46)
    root.right.left.right = newNode(48)
    root.right.right = newNode(52)
    root.right.right.left = newNode(51)
    root.right.right.right = newNode(55)
     
    if(checkThesum(root, path, 0, sum) == 1):
        print("YES")
    else:
        print("NO")
         
# This code is contributed by Srathore

C#

// C# program to check if 
// root to leaf path sum to 
// a given number in BST 
using System;
 
class GFG 
{ 
     
// BST node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
} 
 
/* Helper function that 
allocates a new node */
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if root 
// to leaf path sum to a 
// given number in BST 
static int checkThesum(Node root, int []path, 
                        int i, int sum) 
{ 
    int sum1 = 0, x, y, j; 
     
    if(root == null) 
        return 0; 
         
    // insert the data of a node 
    path[i] = root.data; 
     
    // if the node is leaf 
    // add all the element in array 
    if(root.left == null && 
    root.right == null) 
    { 
        for(j = 0; j <= i; j++) 
            sum1 = sum1 + path[j]; 
             
        // if the sum of root node to leaf 
        // node data is equal then return 1 
        if(sum == sum1) 
            return 1; 
        else
            return 0; 
    } 
 
    x = checkThesum(root.left, path, 
                        i + 1, sum); 
     
    // if x is 1, it means the 
    // given sum is matched with 
    // root to leaf node sum 
    if(x == 1) 
        return 1; 
    else
    { 
        return checkThesum(root.right, path, 
                                i + 1, sum); 
    } 
} 
 
// Driver code 
public static void Main(String []args) 
{ 
    int []path = new int[100];int sum = 164; 
     
    Node root = newNode(45); 
    root.left = newNode(38); 
    root.left.left = newNode(33); 
    root.left.left.left = newNode(31); 
    root.left.left.right = newNode(35); 
    root.left.right = newNode(41); 
    root.left.right.left = newNode(40); 
    root.left.right.right = newNode(44); 
    root.right = newNode(50); 
    root.right.left = newNode(47); 
    root.right.left.left = newNode(46); 
    root.right.left.right = newNode(48); 
    root.right.right = newNode(52); 
    root.right.right.left = newNode(51); 
    root.right.right.right = newNode(55); 
     
    if(checkThesum(root, path, 0, sum) == 1) 
        Console.Write("YES\n"); 
    else
        Console.Write("NO\n"); 
} 
} 
 
// This code is contributed 29AjayKumar

Javascript

<script>
 
// Javascript program to check if 
// root to leaf path sum to 
// a given number in BST 
     
// BST node 
class Node 
{ 
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
} 
 
/* Helper function that 
allocates a new node */
function newNode(data) 
{ 
    var node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if root 
// to leaf path sum to a 
// given number in BST 
function checkThesum(root, path, i, sum) 
{ 
    var sum1 = 0, x, y, j; 
     
    if(root == null) 
        return 0; 
         
    // insert the data of a node 
    path[i] = root.data; 
     
    // if the node is leaf 
    // add all the element in array 
    if(root.left == null && 
    root.right == null) 
    { 
        for(j = 0; j <= i; j++) 
            sum1 = sum1 + path[j]; 
             
        // if the sum of root node to leaf 
        // node data is equal then return 1 
        if(sum == sum1) 
            return 1; 
        else
            return 0; 
    } 
 
    x = checkThesum(root.left, path, 
                        i + 1, sum); 
     
    // if x is 1, it means the 
    // given sum is matched with 
    // root to leaf node sum 
    if(x == 1) 
        return 1; 
    else
    { 
        return checkThesum(root.right, path, 
                                i + 1, sum); 
    } 
} 
 
// Driver code 
var path = Array(100);
var sum = 164; 
 
var root = newNode(45); 
root.left = newNode(38); 
root.left.left = newNode(33); 
root.left.left.left = newNode(31); 
root.left.left.right = newNode(35); 
root.left.right = newNode(41); 
root.left.right.left = newNode(40); 
root.left.right.right = newNode(44); 
root.right = newNode(50); 
root.right.left = newNode(47); 
root.right.left.left = newNode(46); 
root.right.left.right = newNode(48); 
root.right.right = newNode(52); 
root.right.right.left = newNode(51); 
root.right.right.right = newNode(55); 
 
if(checkThesum(root, path, 0, sum) == 1) 
    document.write("YES<br>"); 
else
    document.write("NO<br>"); 
 
// This code is contributed by itsok.
</script>

Output

YES

Complexity Analysis:

Time complexity: O(n) where n is no of nodes in given BST
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!