Thread: Beginner's question

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    20

    Question Beginner's question

    Here's a sample code I came up for the following question :

    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.


    Strategy: subtract the node value from the sum when recurring down,
    and check to see if the sum is 0 when you run out of tree.
    *


    Code:
    int subsums (TREE T, int sum){
    
    if (T==NULL){
    return (sum); 
    }
    else{
    int subsum = sum - T->element; 
    return (subsums(T->left, subsum) && subsums(T->right, subsum));
    }// else
    }

    if sum!=0 why is the result always printed as 1?
    int => it should print any value right? or does is convert to boolean ?

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    20

    Question Can any one please explain this

    For the same question above, the solution given was:

    Code:
    int hasPathSum(struct tree_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->element; 
        return(hasPathSum(node->left, subSum) || 
               hasPathSum(node->right, subSum)); 
      } 
    }
    I don't understand how if (node ==NULL) return (sum ==0) checks the logic (if sum == 0). Any help is greatly appreciated.

  3. #3
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    The best thing to do in this case I think would be to take a sheet a paper, draw a tree on it, and run the algorithm by hand. You'll see what the NULL part if for.

    Basically, it checks that, once you reached a leaf, the accumulated sum is equal to the sum you began with.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginner's Question on QT
    By unix7777 in forum C++ Programming
    Replies: 1
    Last Post: 11-30-2008, 05:53 PM
  2. beginner's question :D
    By kingliaho in forum C Programming
    Replies: 5
    Last Post: 10-17-2008, 05:20 PM
  3. beginner's question about C
    By Roberto Llovera in forum C Programming
    Replies: 5
    Last Post: 02-26-2004, 05:14 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM