# LeetCode Convert BST to Greater Tree: how to do without GenServer?

I simply could not figure out a way to solve this problem without using a GenServer to keep the state of the running sum. My solution with GenServer is below, but I’m wondering if anyone could suggest a way to do it without a GenServer, which felt like overkill.

``````  use GenServer

def init(tally), do: {:ok, tally}

def handle_call(:tally, _from, tally), do: {:reply, tally, tally}

@spec convert_bst(root :: TreeNode.t | nil) :: TreeNode.t | nil
def convert_bst(root) do
{:ok, pid} = GenServer.start(__MODULE__, 0)
do_convert(root, pid)
end

def do_convert(nil, tally), do: nil
def do_convert(node, tally) do
right = do_convert(node.right, tally)
new_val = GenServer.call(tally, :tally)
left = do_convert(node.left, tally)
%TreeNode{ val: new_val, left: left, right: right}
end
``````

I have no ideia how to implement such algorithm, but!
Genservers are an abstraction over a looping receiver, so you can try to implement it with recursion, keeping the state as a parameter and keep passing it. Start with the base cases that returns a value instead of recusing. I bet it will look closely to your current implementation,but without the genserver specifics

1 Like

The GenServer lets `do_convert` do two things:

• return a new tree node
• as a side-effect, update the running total

To remove it, you’ll need to transform that side-effect into a part of the return value.

Consider `Map.pop` for inspiration; it returns a `{popped_value, updated_map}` tuple. You can combine it with rebinding to get code that looks almost like mutability:

``````things = %{a: 1, b: 2, c: 3}

{c_value, things} = Map.pop(things, :c)
``````

A similar transformation on `do_convert` would make it return a tuple of `{tree_node, updated_tally}`.

2 Likes

Many thanks. I knew there must be some way to keep that “state” without using a GenServer. My first issue had actually been figuring out how to use the left node value as the tally for the grandparent node calculation. I only figured that out after changing to GenServer which made the steps in the process clearer to me. Changing to returning tuples was trivial. Thanks again.

``````  def convert_bst(root) do
do_convert(root, 0) |> elem(0)
end

def do_convert(nil, tally), do: {nil, tally}
def do_convert(node, tally) do
{right, interim_tally} = do_convert(node.right, tally)
new_val = interim_tally + node.val
{left, final_tally} = do_convert(node.left, new_val)
{%TreeNode{ val: new_val, left: left, right: right}, final_tally}
end
``````
2 Likes

I came up with a similar solution, and it passed the tests:

``````defmodule Solution do
@spec convert_bst(root :: TreeNode.t | nil) :: TreeNode.t | nil
def convert_bst(root) do
{converted, _} = do_convert_bst(root, 0)
converted
end

defp do_convert_bst(nil, _carry), do: {nil, 0}
defp do_convert_bst(node, carry) do
{right, sum_r} = do_convert_bst(node.right, carry)
carry = carry + node.val + sum_r
{left, sum_l} = do_convert_bst(node.left, carry)
{%TreeNode{left: left, right: right, val: carry}, node.val + sum_l + sum_r}
end
end
``````

`carry` is the sum of the values of all the nodes that have already been visited that have values greater than the next node to visit.

2 Likes

There are many problems in Leetcode with the topic `Design` that you can’t do without using GenServer

1 Like