Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
Given a Binary Search Tree (BST), convert it to a Binary Tree such that every key of the original BST is changed to key plus sum of all greater keys in BST.
When a BST is being traversed in reverse Inorder, for every key currently being visited, all keys that are already visited are all greater keys.
Read full article from Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
Given a Binary Search Tree (BST), convert it to a Binary Tree such that every key of the original BST is changed to key plus sum of all greater keys in BST.
Input: Root of following BST 5 / \ 2 13 Output: The given BST is converted to following Binary Tree 18 / \ 20 13Solution: Do reverse Inoorder traversal. Keep track of the sum of nodes visited so far. Let this sum besum. For every node currently being visited, first add the key of this node to sum, i.e. sum = sum +node->key. Then change the key of current node to sum, i.e., node->key = sum.
When a BST is being traversed in reverse Inorder, for every key currently being visited, all keys that are already visited are all greater keys.
// A recursive function that traverses the given BST in reverse inorder and
// for every key, adds all greater keys to it
void
addGreaterUtil(
struct
node *root,
int
*sum_ptr)
{
// Base Case
if
(root == NULL)
return
;
// Recur for right subtree first so that sum of all greater
// nodes is stored at sum_ptr
addGreaterUtil(root->right, sum_ptr);
// Update the value at sum_ptr
*sum_ptr = *sum_ptr + root->key;
// Update key of this node
root->key = *sum_ptr;
// Recur for left subtree so that the updated sum is added
// to smaller nodes
addGreaterUtil(root->left, sum_ptr);
}
// A wrapper over addGreaterUtil(). It initializes sum and calls
// addGreaterUtil() to recursivel upodate and use value of sum
void
addGreater(
struct
node *root)
{
int
sum = 0;
addGreaterUtil(root, &sum);
}
int
sum_so_far = 0;
void
convert_bst_to_bt_helper(Node* root)
{
if
(root->right != NULL)
convert_bst_to_bt_helper(root->right);
root->data += sum_so_far;
sum_so_far = root->data;
if
(root->left != NULL)
convert_bst_to_bt_helper(root->left);
}