This post is part of the Algorithms Problem Solving series.
Problem description
This is the Binary Search Tree to Greater Sum Tree problem. The description looks like this:
Given the root of a binary search tree with distinct values, modify it so that every node
has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val
.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Examples
Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Solution
My first approach was to traverse the tree to get the sum of all node values and all the node values.
def sum_and_list(node, total, values):
left_total = 0
right_total = 0
left_values = []
right_values = []
if node.left:
[left_total, left_values] = sum_and_list(node.left, total, values)
if node.right:
[right_total, right_values] = sum_and_list(node.right, total, values)
return [
total + left_total + node.val + right_total,
values + left_values + [node.val] + right_values
]
Then I built a hash map to map a node value to the greater sum it can have. So, for the example above, it would have this illustration:
{
0: 36,
1: 36,
2: 35,
3: 33,
4: 30,
5: 26,
6: 21,
7: 15,
8: 8,
}
The hash map creation algorithm is pretty simple:
smaller_total = 0
mapper = {}
for value in values:
mapper[value] = total - smaller_total
smaller_total += value
Now I can use this hash map to modify each tree node. So, I traverse the tree again and update the node value with the value in the hash map. And then just return the root with all the tree modified.
def modify_helper(node, mapper):
if node.left:
modify_helper(node.left, mapper)
if node.right:
modify_helper(node.right, mapper)
node.val = mapper[node.val]
return node
The bst_to_gst
calls all the functions we built and return the modified node.
def bst_to_gst(root):
[total, values] = sum_and_list(root, 0, [])
smaller_total = 0
mapper = {}
for value in values:
mapper[value] = total - smaller_total
smaller_total += value
return modify_helper(root, mapper)
We could also build a reversed in order tree traversal. So the algorithm will start with the rightmost node and then go to the left side. We increment the value
as we traverse the tree.
value = 0
def bst_to_gst(node):
if node.right:
bst_to_gst(node.right)
node.val = node.val + value
value = node.val
if node.left:
bst_to_gst(node.left)
return node
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course
Top comments (0)