Algorithms Problem Solving: Tree to greater sum
Tags: algorithms, python, computerscience, interview
Published: 2020-06-08 11:22:03

---
title: Algorithms Problem Solving: Tree to greater sum
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/mapple.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/tree-to-greater-sum.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem description

This is the [Binary Search Tree to Greater Sum Tree](https://leetcode.com/problems/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

```python
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. 

```python
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:

```python
{
  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:

```python
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.

```python
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.

```python
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.

```python
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](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Stack Data Structure](https://leandrotk.github.io/tk/2020/01/stack-data-structure/index.html)
- [Queue Data Structure](https://leandrotk.github.io/tk/2020/01/queue-data-structure/index.html)
- [Linked List](https://leandrotk.github.io/tk/2020/02/linked-list/index.html)
- [Tree Data Structure](https://leandrotk.github.io/tk/2020/02/tree-data-structure/index.html)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)
- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)