How to recurse and build a key to access a child node

Questions / Help
,
1

Hi,

So I’m new to Elixir and I’m struggling with a recursion question. I have a tree structure (of structs, with ordered lists of children), where each node has a single parent and many children. it can be nested to an arbitrary depth.

tree = %{
    id: "a",
    children: [
        %{ 
          id: "one",
          children: [
            %{ 
              id: "two"
            }
          ]
        },
        %{ 
          id: "three",
          children: [
            %{ 
              id: "four"
            },
            %{ 
              id: "five"
            },
          ]
        },
    ]
}

I’m trying to write a recursive function that will build an access key to a given node, identified by its ID.

Tree.path_to(tree, id, path \\ [])
``

So for example id "five", would return the following, which I can then use with the kernel's get_in and update_in functions.

[:children, Acess.to(1), :children, Access.to(1)]


I'm just too new to Elixir (and functional programming in general) to work it out so any help would be appreciated!
2

Hi dredison! Was going to give you a partial solution for your learning but I pretty much solved it:

# When parameters appear multiple times they are checked for equality.
def path_to(%{id: id}, id), do: []

def path_to(%{children: [_ | _] = children}, id) do
  case subpath_to(children, id) do
    {idx, path} -> [:children, idx | path]
    _ -> nil
  end
end

def path_to(_, _), do: nil

def subpath_to(children, id) do
  Enum.reduce_while(children, 0, fn child, idx ->
    path = path_to(child, id)
    if path, do: {:halt, {idx, path}}, else: {:cont, idx + 1}
  end)
end

You still have to do something to get the desired format. :slightly_smiling_face:

Tip: When writing recursive functions it always helps to handle the basic cases first and to make sure that there’s a terminating clause. Then you build on that and work your way down to the nested structures and see if you can use the functions that handle the basic cases.

1 Like
3

Hey Aziz,

Amazing, thank you. Works like a charm. It’s also pointed me towards a better understanding of pattern matching and function arguments. Thanks again.

1 Like