Remove all nodes which don’t lie in any path with sum>= k

1) pass sum of root to its children
2) compare at each level wether we have got desired sum
  {
    i) if yes, return true from that node
    ii) else check if node is leaf node
      {
       a) if its a leaf node & sum is not desired one return false
     }
   pass sum upto this node to left subtree
   if left subtree return false
      remove left subtree node
   pass sum upto this node to right subtree
   if right subtree return false
      remove right subtree node
   if either of subtree has return tree
      return true
   else
     return false

	bool prunTree (tree *root, int sum, int K)
	{
	if (!root)
	return false;
	if (root->key + sum >= K)
	{
	return true;
	}
	if (!root->left && !root->right && ((root->key + sum) < K))
	{
	return false;
	}
	bool l_ret = prunTree (root->left, (root->key + sum), K);
	if (l_ret == false)
	{
	if (root->left)
	free (root->left);
	root->left = NULL;
	}
	bool r_ret = prunTree (root->right, (root->key + sum), K);
	if (r_ret == false)
	{
	if (root->right)
	free (root->right);
	root->right = NULL;
	}
	if (l_ret == true || r_ret == true)
	return true;
	else
	return false;
	}
	void pruning (tree **root, int K)
	{
	if (!*root)
	return;
	if ((*root)->key >= K)
	return;
	bool ret = prunTree (*root, 0, K);
	if (ret == false)
	{
	free (*root);
	*root = NULL;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub