Hello everyone, I'm trying to write a function that returns an array with all path

General Usage
1

Hello everyone,
I’m trying to write a function that returns an array with all paths from root to leaves in a binary tree, where each path is an array of symbols.
The tree struct is defined like this:

abstract type Node end

struct Branch_Node <: Node
    left::Node
    right::Node
end

struct Leaf_Node <: Node
end

So for this tree

tree = Branch_Node(Branch_Node(Branch_Node(Leaf_Node(), Leaf_Node()), Leaf_Node()),Branch_Node(Leaf_Node(), Leaf_Node()))

I want the function to return

[[:left, :left, :left], [:left, :left, :right], [:left, :right], [:right, :left], [:right, :right]]

I can write a function that returns a nested array like this:

function get_path_to_leaf(node::Leaf_Node)
    return
end
function get_path_to_leaf(node::Branch_Node)
    return [[:left, get_path_to_leaf(node.left)], [:right, get_path_to_leaf(node.right)]]
end

But I can’t figure out how to unfold the paths into flat arrays. I though something like this:

function get_path_to_leaf(node::Leaf_Node)
    return []
end

function get_path_to_leaf(node::Branch_Node)
    return [[append!([:left], i) for i in get_path_to_leaf(node.left)], [append!([:right], i) for i in get_path_to_leaf(node.right)]]
end

would do it, but I get the following error “ERROR: MethodError: Cannot convert an object of type Array{Symbol,1} to an object of type Symbol”
and I’m having no luck debugging it. Sorry for the wall of text, can anyone help?

Note that the original poster on Slack cannot see your response here on Discourse. Consider transcribing the appropriate answer back to Slack, or pinging the poster here on Discourse so they can follow this thread.
(Original message :slack:) (More Info)

2

I’m not entirely sure, but I don’t think this will work. Anytime you’d reach the leaf, you’d return an empty collection, which would “propagate” and give you an empty collection in the end. I think for something like this to work, you need to return a non-empty thing with the leaf, even if it’s an 1-element vector containing an empty array of symbols:

julia> struct Branch_Node <: Node
           left::Node
           right::Node
       end

julia> struct Leaf_Node <: Node
       end

julia> function get_path_to_leaf(node::Leaf_Node)
           return [Symbol[]]
       end
get_path_to_leaf (generic function with 1 method)

julia> function get_path_to_leaf(node::Branch_Node)
           return [[[:left; x] for x in get_path_to_leaf(node.left)]; [[:right; x] for x in get_path_to_leaf(node.right)]]
       end
get_path_to_leaf (generic function with 2 methods)

julia> tree = Branch_Node(Branch_Node(Branch_Node(Leaf_Node(), Leaf_Node()), Leaf_Node()),Branch_Node(Leaf_Node(), Leaf_Node()))
Branch_Node(Branch_Node(Branch_Node(Leaf_Node(), Leaf_Node()), Leaf_Node()), Branch_Node(Leaf_Node(), Leaf_Node()))

julia> get_path_to_leaf(tree)
5-element Vector{Vector{Symbol}}:
 [:left, :left, :left]
 [:left, :left, :right]
 [:left, :right]
 [:right, :left]
 [:right, :right]
1 Like