Binary Search Tree to Greater Sum Tree

Reverse inorder (right, node, left) with a running sum

time O(n)space O(h) recursion stack

A plain inorder walk visits a BST smallest to largest — useful for sorting, backwards for this problem. Flip the order to right, node, left and the walk visits values LARGEST first. Keep one running sum, add the current node's original value to it, then overwrite the node with that sum: by the time a node is reached, the sum already holds every value strictly greater than it, so adding the node's own value gives exactly "sum of all values >= this one".

Details

Animated on: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] — replace every node's value with the sum of all values greater than or equal to it in the original tree. Expected: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8].

Problem:Binary Search Tree to Greater Sum TreeMedium

Reverse inorder (right, node, left) with a running sum

step 1 / 11

Call reverseInorder(4). A normal inorder walk (left, node, right) visits values smallest first — the wrong direction for a running total of "everything greater or equal". Walking right, node, left instead visits values LARGEST first, so one running sum carries exactly what each node needs.

Pseudocode

1FUNCTION reverseInorder(node):
2  IF node = null:
3    RETURN
4  reverseInorder(node.right)
5  sum <- sum + node.val
6  node.val <- sum
7  reverseInorder(node.left)

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Call reverseInorder(4). A normal inorder walk (left, node, right) visits values smallest first — the wrong direction for a running total of "everything greater or equal". Walking right, node, left instead visits values LARGEST first, so one running sum carries exactly what each node needs.
Right subtree of 8 is done, so every value greater than 8 has already been folded into the running sum (0). Add 8 itself: sum <- 0 + 8 = 8. Overwrite the node: 8 becomes 8.
Right subtree of 7 is done, so every value greater than 7 has already been folded into the running sum (8). Add 7 itself: sum <- 8 + 7 = 15. Overwrite the node: 7 becomes 15.
Right subtree of 6 is done, so every value greater than 6 has already been folded into the running sum (15). Add 6 itself: sum <- 15 + 6 = 21. Overwrite the node: 6 becomes 21.
Right subtree of 5 is done, so every value greater than 5 has already been folded into the running sum (21). Add 5 itself: sum <- 21 + 5 = 26. Overwrite the node: 5 becomes 26.
Right subtree of 4 is done, so every value greater than 4 has already been folded into the running sum (26). Add 4 itself: sum <- 26 + 4 = 30. Overwrite the node: 4 becomes 30.
Right subtree of 3 is done, so every value greater than 3 has already been folded into the running sum (30). Add 3 itself: sum <- 30 + 3 = 33. Overwrite the node: 3 becomes 33.
Right subtree of 2 is done, so every value greater than 2 has already been folded into the running sum (33). Add 2 itself: sum <- 33 + 2 = 35. Overwrite the node: 2 becomes 35.
Right subtree of 1 is done, so every value greater than 1 has already been folded into the running sum (35). Add 1 itself: sum <- 35 + 1 = 36. Overwrite the node: 1 becomes 36.
Right subtree of 0 is done, so every value greater than 0 has already been folded into the running sum (36). Add 0 itself: sum <- 36 + 0 = 36. Overwrite the node: 0 becomes 36.
Every node visited once, largest to smallest, one running sum away from the answer: 8->8, 7->15, 6->21, 5->26, 4->30, 3->33, 2->35, 1->36, 0->36. O(n) time, O(h) recursion stack — no second pass and no extra array needed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Search Tree to Greater Sum Tree in the editor All BST problems Back to roadmap