http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
Thursday, December 12, 2013
Wednesday, December 11, 2013
Thursday, December 5, 2013
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } |
Subscribe to:
Posts (Atom)