Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node. For example, consider the following BST.
50
/
30 70
/ /
20 40 60 80
The above tree should be modified to following
260
/
330 150
/ /
350 300 210 80
A simple method for solving this is to find sum of all greater values for every node. This method would take O(n^2) time.
We can do it using a single traversal. The idea is to use following BST property. If we do reverse Inorder traversal of BST, we get all nodes in decreasing order. We do reverse Inorder traversal and keep track of the sum of all nodes visited so far, we add this sum to every node.
C
// C program to add all greater values in every node of BST #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *left, *right; }; // A utility function to create a new BST node struct Node *newNode(int item) { struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp->data = item; temp->left = temp->right = NULL; return temp; } // Recursive function to add all greater values in every node void modifyBSTUtil(struct Node *root, int *sum) { // Base Case if (root == NULL) return; // Recur for right subtree modifyBSTUtil(root->right, sum); // Now *sum has sum of nodes in right subtree, add // root->data to sum and update root->data *sum = *sum + root->data; root->data = *sum; // Recur for left subtree modifyBSTUtil(root->left, sum); } // A wrapper over modifyBSTUtil() void modifyBST(struct Node *root) { int sum = 0; modifyBSTUtil(root, &sum); } // A utility function to do inorder traversal of BST void inorder(struct Node *root) { if (root != NULL) { inorder(root->left); printf("%d ", root->data); inorder(root->right); } } /* A utility function to insert a new node with given data in BST */struct Node* insert(struct Node* node, int data) { /* If the tree is empty, return a new node */ if (node == NULL) return newNode(data); /* Otherwise, recur down the tree */ if (data <= node->data) node->left = insert(node->left, data); else node->right = insert(node->right, data); /* return the (unchanged) node pointer */ return node; } // Driver Program to test above functions int main() { /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ struct Node *root = NULL; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); modifyBST(root); // print inoder tarversal of the modified BST inorder(root); return 0; } |
Java
// Java code to add all greater values to // every node in a given BST // A binary tree node class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; } } class BinarySearchTree { // Root of BST Node root; // Constructor BinarySearchTree() { root = null; } // Inorder traversal of the tree void inorder() { inorderUtil(this.root); } // Utility function for inorder traversal of // the tree void inorderUtil(Node node) { if (node == null) return; inorderUtil(node.left); System.out.print(node.data + " "); inorderUtil(node.right); } // adding new node public void insert(int data) { this.root = this.insertRec(this.root, data); } /* A utility function to insert a new node with given data in BST */ Node insertRec(Node node, int data) { /* If the tree is empty, return a new node */ if (node == null) { this.root = new Node(data); return this.root; } /* Otherwise, recur down the tree */ if (data <= node.data) { node.left = this.insertRec(node.left, data); } else { node.right = this.insertRec(node.right, data); } return node; } // This class initialises the value of sum to 0 public class Sum { int sum = 0; } // Recursive function to add all greater values in // every node void modifyBSTUtil(Node node, Sum S) { // Base Case if (node == null) return; // Recur for right subtree this.modifyBSTUtil(node.right, S); // Now *sum has sum of nodes in right subtree, add // root->data to sum and update root->data S.sum = S.sum + node.data; node.data = S.sum; // Recur for left subtree this.modifyBSTUtil(node.left, S); } // A wrapper over modifyBSTUtil() void modifyBST(Node node) { Sum S = new Sum(); this.modifyBSTUtil(node, S); } // Driver Function public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); tree.modifyBST(tree.root); // print inoder tarversal of the modified BST tree.inorder(); } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to add all greater values # in every node of BST # A utility function to create a # new BST node class newNode: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Recursive function to add all greater # values in every node def modifyBSTUtil(root, Sum): # Base Case if root == None: return # Recur for right subtree modifyBSTUtil(root.right, Sum) # Now Sum[0] has sum of nodes in right # subtree, add root.data to sum and # update root.data Sum[0] = Sum[0] + root.data root.data = Sum[0] # Recur for left subtree modifyBSTUtil(root.left, Sum) # A wrapper over modifyBSTUtil() def modifyBST(root): Sum = [0] modifyBSTUtil(root, Sum) # A utility function to do inorder # traversal of BST def inorder(root): if root != None: inorder(root.left) print(root.data,end=" ") inorder(root.right) # A utility function to insert a new node # with given data in BST def insert(node, data): # If the tree is empty, return a new node if node == None: return newNode(data) # Otherwise, recur down the tree if data <= node.data: node.left = insert(node.left, data) else: node.right = insert(node.right, data) # return the (unchanged) node pointer return node # Driver Code if __name__ == '__main__': # Let us create following BST # 50 # / # 30 70 # / / # 20 40 60 80 root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) modifyBST(root) # print inoder tarversal of the # modified BST inorder(root) # This code is contributed by PranchalK |
C#
using System; // C# code to add all greater values to // every node in a given BST // A binary tree node public class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; } } public class BinarySearchTree { // Root of BST public Node root; // Constructor public BinarySearchTree() { root = null; } // Inorder traversal of the tree public virtual void inorder() { inorderUtil(this.root); } // Utility function for inorder traversal of // the tree public virtual void inorderUtil(Node node) { if (node == null) { return; } inorderUtil(node.left); Console.Write(node.data + " "); inorderUtil(node.right); } // adding new node public virtual void insert(int data) { this.root = this.insertRec(this.root, data); } /* A utility function to insert a new node with given data in BST */ public virtual Node insertRec(Node node, int data) { /* If the tree is empty, return a new node */ if (node == null) { this.root = new Node(data); return this.root; } /* Otherwise, recur down the tree */ if (data <= node.data) { node.left = this.insertRec(node.left, data); } else { node.right = this.insertRec(node.right, data); } return node; } // This class initialises the value of sum to 0 public class Sum { private readonly BinarySearchTree outerInstance; public Sum(BinarySearchTree outerInstance) { this.outerInstance = outerInstance; } public int sum = 0; } // Recursive function to add all greater values in // every node public virtual void modifyBSTUtil(Node node, Sum S) { // Base Case if (node == null) { return; } // Recur for right subtree this.modifyBSTUtil(node.right, S); // Now *sum has sum of nodes in right subtree, add // root->data to sum and update root->data S.sum = S.sum + node.data; node.data = S.sum; // Recur for left subtree this.modifyBSTUtil(node.left, S); } // A wrapper over modifyBSTUtil() public virtual void modifyBST(Node node) { Sum S = new Sum(this); this.modifyBSTUtil(node, S); } // Driver Function public static void Main(string[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); tree.modifyBST(tree.root); // print inoder tarversal of the modified BST tree.inorder(); } } // This code is contributed by Shrikant13 |
Output
350 330 300 260 210 150 80
Time Complexity: O(n) where n is number of nodes in the given BST.
As a side note, we can also use reverse Inorder traversal to find kth largest element in a BST.
leave a comment
0 Comments