Given a binary tree, defining a term “complete path sum” as sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, prune the nodes for whose complete path sum is smaller than k

#include <stdio.h>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

  explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {}

  ~TreeNode() {
    delete left;
    delete right;
    
    left = NULL;
    right = NULL;  
  }

  private:
    TreeNode(const TreeNode&);
    TreeNode operator=(const TreeNode&);
};

typedef TreeNode* Tree;

bool pruneTree(Tree t, int k, int sum) 
{
  if (t == NULL) return sum < k;
  
  sum += t->el;

  bool l = pruneTree(t->left, k, sum);
  bool r = pruneTree(t->right, k, sum);

  if (l) {
    delete(t->left);  
    t->left = NULL;
  } 

  if (r) {
    delete(t->right);  
    t->right = NULL;
  } 

  return l && r;
} 

Tree pruneTree(Tree t, int k) 
{
  if (pruneTree(t, k, 0)) {
    delete t;
    return NULL;  
  }  

  return t;
}

void preorder(Tree t)
{
  if (t == NULL) return;
  printf("%d ", t->el);
  preorder(t->left);  
  preorder(t->right);  
}

/*
  Example Tree:

          1
       /    \
      2      3
     / \    /  \
    4   5  6    7
   /     \     / 
  8       9   10

*/

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();
  preorder(pruneTree(t, 17));
  printf("\n");
  return 0;
}
Advertisements

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