CODEWITHSUNDEEP
c++recursiontreebinary-tree
brainydexter
brainydexter

Reputation: 20356

do i need to traverse both subtrees for computing, the root to leaf sum, to a given value?

This is the problem statement:

"Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum."

I implemented it like this:

int hasPathSum(Node* node, int sum) {
    if(node == NULL)
        return sum == 0;

    int diff = sum - node->data;

    if(diff < 0) return 0;

    if(diff == 0)
        return node->left == NULL && node->right == NULL ? 1 : 0;

    if(diff < node->data)
        return hasPathSum(node->left, diff);
    else
        return hasPathSum(node->right, diff);
}

I only traverse 1 sub-tree and not both, depending on the difference of (sum - node->data).

However, the recommended solution required traversing both the subtrees like this:

int hasPathSum(Node* node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == NULL) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node->data; 
    return(hasPathSum(node->left, subSum) || 
           hasPathSum(node->right, subSum)); 
  } 
}

I don't see why do we have to traverse both the subtrees ?

Here is the source of the problem: Problem 7

EDIT:

Bad assumption on my part that the tree is a BST. Its just a binary tree.

However, if it were a BST, I'd like to hear some feedback on my implementation ? Would it not be better to do it the way I did it than the other solution ? (which is a little unfair to compare since that solution is for any binary tree)

EDIT solution:

Please see anatolyg's response here which explains the problem with my proposed solution. Thanks anatolyg.

Upvotes: 0

Views: 258

Answers (4)

anatolyg
anatolyg

Reputation: 28251

The special arrangement of the nodes in the binary search tree only helps in searching for a number, not for a sum. Imagine a very big tree, with depth of like 100, having the sought-for path along all the left nodes, and the target sum moderately big (e.g. 1+2+3+...+100).

When your algorithm starts from the root, the diff will be large, and it will go to the right branch of the tree, where the sum doesn't necessarily exist (e.g. all elements there are greater than 1000000000, so too big).

Upvotes: 2

user1512399
user1512399

Reputation:

Consider a binary tree with root node with data 1. The root node has two subtrees, the left holds 2, and the right holds 3. The node 2 has a left subtree of 5.

If you ask if a path from the overall root to a leaf node can add up to a sum of 8, the answer is yes.

overall root = 1, left subtree = 2, left subtree = 5, which adds up to 8. However, you don't know ahead of time which path will add up to the correct sum if any, so you must go down both subtrees recursively.

Binary tree code should be short. Use the recursive nature of binary trees and the fact that a tree is either null or it has left and right subtrees.

Upvotes: 1

elyashiv
elyashiv

Reputation: 3691

the tree isn't a search tree and there for, you don't know any thing about the child’s data from the fathers data.

Upvotes: 0

Ben Jackson
Ben Jackson

Reputation: 93770

Your problem statement doesn't mention anything about how the tree is arranged, so I don't appreciate what your left/right test is trying to do. You can't know anything about the contents of the node->left or node->right subtrees without testing them.

Also, in the suggested solution the || is going to short-circuit if the left subtree matches, so you are not necessarily traversing both subtrees. You only traverse the entire tree if there is no path: you obviously have to test every path to be sure there isn't one. (Ok, you also traverse the entire tree if you find a match on the final path...)

Upvotes: 2

Related Questions