Pattern visualizer

BST to Greater Sum Tree

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". 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]..

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

time O(n)space O(h) recursion stackstep 1 / 11

line 1

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap