Find Binary Tree Path Sum

Question

I am trying to resolve following problem. Please advice which part of the code can be improved.

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example: Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct stTree
{
    struct stTree * left;
    struct stTree * right;
    int value;
} stTree;

struct stTestCase
{
   stTree *root;
   int sum;
   bool result;
};

stTree* createNode(int value, stTree *leftNode, stTree *rightNode)
{
    stTree *node = malloc(sizeof *node);
    if (!node) abort();
    node->left = leftNode;
    node->right = rightNode;
    node->value = value;
    return node;
}

bool hasPathSum(const stTree *root, int sum)
{
    if (!root) return false;

    if (!root->left && !root->right)
    {
        if (sum == root->value)
            return true;
        else
            return false;
    }
    return (hasPathSum(root->left, sum - root->value)
      | hasPathSum(root->right, sum - root->value));
}

static stTree* findBottomLeft(stTree *node)
{
    while (node->left)
        node = node->left;
    return node;
}

void freeTree(stTree *node)
{
    if (!node) return true;
    stTree *bottomLeft = findBottomLeft(node);

    while (node)
    {
        if (node->right)
        {
            bottomLeft->left = node->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        stTree *old = node;
        node = node->left;
        free(old);
    }
}

int main(void)
{

   struct stTestCase test_cases[3]={
        {
           createNode(5,
            createNode(4,
                createNode(11,
                    createNode(7, NULL, NULL),
                    createNode(2, NULL, NULL)), NULL),
            createNode(8,
                createNode(13, NULL, NULL),
                createNode(4, NULL,
                    createNode(1, NULL, NULL)))),
            22,
            true
         },
         {
            createNode(5,
             createNode(1,
                 createNode(11,
                     createNode(3, NULL, NULL),
                     createNode(2, NULL, NULL)), NULL),
             createNode(7,
                 createNode(13, NULL, NULL),
                 createNode(4, NULL,
                     createNode(1, NULL, NULL)))),
            22,
            false
          },
          {
             createNode(12,
              createNode(4,
                  createNode(11,
                      createNode(7, NULL, NULL),
                      createNode(51, NULL, NULL)), NULL),
              createNode(8,
                  createNode(13, NULL, NULL),
                  createNode(4, NULL,
                      createNode(6, NULL, NULL)))),
               22,
               false
           }
   };

   for(int i=0; i<3; i++)
   {
      if (hasPathSum(test_cases[i].root, test_cases[i].sum)  == test_cases[i].result)
         printf("test case [%d], PASS\n", i);
      else
        printf("test case [%d], FAIL\n", i);
      freeTree(test_cases[i].root);
   }

}

RESULT:

test case [0], PASS

test case [1], PASS

test case [2], PASS

Toby Speight · Accepted Answer · 2020-12-02 11:50:20Z

We don't normally do this in real (non-toy) programs:

stTree *node = malloc(sizeof *node);
if (!node) abort();

It's convenient and probably okay for a simple exercise like this, though.

Code of the form if (c) then return true; else return false; simplifies to just return c;, so we can reduce

    if (sum == root->value)
        return true;
    else
        return false;

to just

    return sum == root->value;

I think we can do better than that, if we're happy to consider an empty tree as having a sum of zero:

bool hasPathSum(const stTree *node, int sum)
{
    if (!node) {
        return sum == 0;
    }

    sum -= node->value;
    return hasPathSum(node->left, sum) || hasPathSum(node->right, sum);
}

Notice that I've used || rather than | in my version - there's no need to continue looking once we've found a successful result. Also, because this function is recursive, the name root is misleading for the parameter - it could be any node, and it's only the root in the top-level call.

void freeTree(stTree *node)
{
    if (!node) return true;

That's a simple error - can't return a value from a function declared void(...). That suggests you're not enabling enough compiler warnings.

Good to see unit tests. I'm not sure I'd pile all the test data together like that - I'd probably create a small function for each test, so that each test is independent. Consider using one of the available test frameworks to help relieve the repetitive work of testing.

When writing tests, it's a good idea to write the smallest test you can think of (e.g. the null tree) as the first test, and start with it failing (so you know the test works). Then make it pass, and write the next simplest failing tests (tree with one node - make sure you test calls that should return different values).

Here's how I would begin (using Google Test, which is C++, but it's easy to test C code by using extern "C"):

#include <gtest/gtest.h>

extern "C" {
    struct stTree;

    stTree* createNode(int value, stTree *leftNode, stTree *rightNode);
    bool hasPathSum(const stTree *node, int sum);
    void freeTree(stTree *node);
}

TEST(PathSum, empty)
{
    stTree *tree = NULL;
    EXPECT_FALSE(hasPathSum(tree, 1));
    EXPECT_TRUE(hasPathSum(tree, 0));
}

TEST(PathSum, one_node)
{
    stTree *tree = createNode(2, NULL, NULL);
    EXPECT_FALSE(hasPathSum(tree, 0));
    EXPECT_TRUE(hasPathSum(tree, 2));
}

TEST(PathSum, two_nodes)
{
    stTree *tree = createNode(2, NULL,
                              createNode(3, NULL, NULL));
    EXPECT_FALSE(hasPathSum(tree, 0));
    EXPECT_TRUE(hasPathSum(tree, 2));
    EXPECT_TRUE(hasPathSum(tree, 5));
}

Thanks. So what would you do to allocate memory in real life software. — Erdenebat Ulziisaikhan
– Erdenebat Ulziisaikhan, Commented Dec 1, 2020 at 6:56
The allocation would be exactly the same. It's the abort() that would be different - we'd hope to be able to recover gracefully. That would mean returning a null pointer from that function, so that the caller could choose how to deal with the problem. — Toby Speight
– Toby Speight, Commented Dec 1, 2020 at 8:43

dmuir · Accepted Answer · 2020-12-02 14:36:10Z

Good code.

A few comments:

I'd recommend getting into the habit of always using {..} after an if etc, even when they are not required. It's very easy to add code to a clause after an if, and forget to add the braces, so breaking the program. So instead of

if (!node) abort();

I'd write

if (!node) 
{  abort();
}

freeTree() seems a bit complex to me. This seems simpler:

void    freeTree(stTree *node)
{   if ( node)
    {   freeTree( node->left);
        freeTree( node->right);
        free( node);
    }
}

There are two occurrences of the number of test cases in the program. It would be easy to forget to change at least one of them when you add/delete a test case. This could be eliminated by having the definition read

struct stTestCase test_cases[]={

(ie let the compiler figure out how many there are) and then the loop could be

int ncases = sizeof test_cases / sizeof test_cases[0];
    for(int i=0; i<ncases; i++)

Your main is declared to return an int, but has no return statement.

Stack Exchange Network

Find Binary Tree Path Sum

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Find Binary Tree Path Sum

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions