Convert BST to Greater Sum Tree

Objective: Given a binary search tree (BST), convert it into greater sum tree.

What is greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.  see the example below

Convert BST to Greater Sum Tree



Naive approach will be for every node, traverse the tree and find out all the nodes which are greater and update the node. This approach is fine but only problem with this approach is the Time Complexity will be O(N^2). We can do it in one traversal.

We know that right most node in the binary search tree is the biggest node among all node so we will start from there, (reverse inorder traversal).

  1. Since we are visiting the nodes in the decreasing order so all we need to care about maintaining the sum of the nodes visited.
  2. Keep a global variable which maintains the sum of the nodes visited till now.
  3. Before updating the node value, store it in temp, we need it later
  4. Updated the node value as sum ( since each node contains sum of nodes greater than that node which means we need to exclude the node value itself).
  5. Update the sum as sum = sum + temp (for the next node in iteration).
  6. See the code for better understanding.

Complete Code:


2  5  7  10  12  15  20
69  64  57  47  35  20  0

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.