CareerCup4.9.cpp

CareerCup4.9.cpp

/*
 Chapter 4
 
 4.9 You are given a binary tree in which each node contains an integer
 value (which might be positive or negative). Design an algorithm to
 print all paths which sum to a given value. The path does not need
 to start or end at the root or a leaf, but it must go in a straight
 line down.
 */

#include <iostream>
#include <algorithm>  // for max()
#include <climits>    // for INT_MIN

using namespace std;

//-------------------
// Tree node struct
//-------------------
typedef struct tNode {
    int value;
    struct tNode* left;
    struct tNode* right;
}tNode;

tNode* newNode(int v)
{
    tNode* node = new tNode;
    node->value = v;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Utility Functions' Prototype
void findpath(tNode* root, int sum, int path[], int level);  // General case
void findpathRootStart(tNode* root, int sum, int path[], int level);  // Simplified case
void printPath(int path[], int start, int end);
int getHeight(tNode* root);
tNode* newBT();

//-----------------------------------------
// Print all paths which sum to given value
//-----------------------------------------
void allSumPaths(tNode* root, int sum)
{
    // need to define a path array to store
    int height = getHeight(root);
    // path[0] ~ path[height]
    int path[height + 1];
    cout << "-----------General Case----------" << endl;
    cout << "      (Start from anywhere)      " << endl;
    findpath(root, sum, path, 0); 
    cout << "-----------Simplified Case----------" << endl;
    cout << "          (Start from root)         " << endl;
    findpathRootStart(root, sum, path, 0);
}

//-------------------
// Utility functions
//-------------------
// Recursively find paths - start and end from anywhere
void findpath(tNode* root, int sum, int path[], int level)
{
    if (root == NULL)
        return;
    path[level] = root->value;
    
    int current = 0;
    for (int i = level; i >= 0; --i)  // Note: if use increase pattern, i and level will be the same in the end
                                      //       and printPath() has no range to print. [Tricky part]
    {
        current += path[i];
        // if condition must inside for loop
        // to ensure every time current = sum
        // we print the path
        if (current == sum)
            printPath(path, i, level);  // Note: path[i] ~ path[level] will be printed
                                        //       If we don't reset path[level]:
                                        //         - path[0] will always be root value
                                        //         - path[value] will be updated when recursing
    }
    // recurse on left and right sub-tree
    findpath(root->left, sum, path, level + 1);
    findpath(root->right, sum, path, level + 1);
    // reset path[level] is good practice
    path[level] = INT_MIN;
}

// Learn More: findpath() variation - only start from root, end anywhere
void findpathRootStart(tNode* root, int sum, int path[], int level)
{
    if (root == NULL)
        return;
    path[level] = root->value;
    
    int current = 0;
    for (int i = level; i >= 0; --i)
    {
        current += path[i];
    }
    // we only need to move if statement out of for loop
    // we can achieve our goal
    if (current == sum)
        printPath(path, 0, level);
    
    findpathRootStart(root->left, sum, path, level + 1);
    findpathRootStart(root->right, sum, path, level + 1);
    path[level] = INT_MIN;
}

// Print out path
void printPath(int path[], int start, int end)
{
    for (int i = start; i <= end; ++i)
    {
        if (i != end)
            cout << path[i] << " -> ";
        else
            cout << path[i] << endl;
    }
}

// Get the height of a binary tree
int getHeight(tNode* root)
{
    if (root == NULL || (!root->left && !root->right))
        return 0;
    else
        return 1 + max(getHeight(root->left), getHeight(root->right));
}

// Generate a test binary tree
tNode* newBT()
{
    tNode* root = newNode(1);
    tNode* one_l = newNode(2); tNode* one_r = newNode(0);
    tNode* two_l = newNode(-1); tNode* two_m = newNode(-2); tNode* two_r = newNode(3);
    tNode* thr_l = newNode(3); tNode* thr_m = newNode(5); tNode* thr_r = newNode(4);
    tNode* four_l = newNode(0);
    root->left = one_l; root->right = one_r;
    one_l->left = two_l; one_r->left = two_m; one_r->right = two_r;
    two_l->right = thr_l; two_m->left = thr_m; two_m->right = thr_r;
    thr_l->left = four_l;
    return root;
}

//-----------------------
// Main Function to test
//-----------------------
int main()
{
    /*      1
          /   \
        2      0
       /      /  \
     -1     -2    3
       \    / \
        3  5   4
       /
      0            */
    tNode* root = newBT();
    int sum = 3;
    cout << "All the paths which sum to " << sum << " :" << endl;
    allSumPaths(root, sum);
    return 0;
}