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

Questions / Help
1

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_cast({:add, n}, tally), do: {:noreply, n + 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)
    GenServer.cast(tally, {:add, node.val})
    new_val = GenServer.call(tally, :tally)
    left = do_convert(node.left, tally)
    %TreeNode{ val: new_val, left: left, right: right}
  end
2

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
3

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
4

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
5

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
6

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

1 Like