Home > Applied Algorithms, Recursion, Tree > Given a binary tree, find a branch whose elements sum up to a given number.

Given a binary tree, find a branch whose elements sum up to a given number.

Problem Statement: You have been given a binary tree with integer values. You are supposed to find if a branch exists  (ROOT node to LEAF node) such that the sum of all the values on this branch sums up to a given number ‘x’.

Let us work on the above binary tree. Assume x=26. Now the correct branch would be 2->7->6->11. So the answer is “Yes, such a branch exists”. I hope you understand the question now.

How would you go about solving this problem? If the first thought that came to your mind was “recursion”, kudos! That is in fact the correct way to solve this question. (And usually always the technique you use in questions involving trees)

This time we go for a top->bottom recursion and keep adding the sum everytime we move down in a branch. Now as soon as you reach the leaf, check your sum and return 1 (success) or 0 (failure) accordingly. Here is the algorithm:

int Check ( Node current, int sum ) //initial call with Check ( ROOT, 0)

{

sum = sum + current->VALUE

If ( current->LEFT != NULL)

int left = Check ( current->LEFT, sum )

If ( current-> LEFT !=NULL)

int right = Check ( current->RIGHT, sum )

If (current->LEFT == current->RIGHT == NULL )

{ //in case of LEAF nodes

If (sum==x)

return 1

Else

return 0

}

return (left || right) //return 1 IFF we receive SUCCESS (1) from any branch, left/right

}

Pretty simple to understand, right? So for the first time in the blog, we have applied recursion and used it while going it from top to bottom (if you get what I mean). 🙂

Cheerio!

PS: If you are wondering why we don’t return as soon as sum exceeds ‘x’, remember that the binary tree is said to have integers, which means negative numbers are allowed. 😉 Attention to detail!

Advertisements
  1. Sangar Jitendra
    October 16, 2013 at 11:44 am

    Hi,
    First of all, nice blog!

    Regarding this blog ,I have written a post on this problem and couple of other related problems.

    http://algorithmsandme.blogspot.in/2013/09/paths-in-binary-search-tree.html

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: