Given a bst replace every node with sum of all nodes which are greater than that node. Replace the maximum value node with 0
Answers
Answered by
2
Answer:
Explanation:
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.
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.
may be it's helpful for you
Attachments:
Similar questions