AbstractTrees needs one more kind of DFS?

General Usage
1

Here is what a PostOrderDFS does

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [1, 2, 3, [2, 3], [1, [2, 3]]] .

but what I want it to do is

[2, 3, [2,3], 1, [1,[2,3]]].

It doesn’t appear that AbstractTrees has a routine that can do that, or am i missing something ?
I’m wondering because there is a lot of “missing docstring” errors in the documentation.
I’ve looked around in the code too, but haven’t found another kind of DFS traversal.
I was trying to avoid writing my own tree traversal…

2

I fail to see the logic in your output, the branch 1 is before the branch [2,3], so it will be explored first. Do you want to explore child in reverse order ? Then you can reverse the PreOrderDFS, bu you will get [3, 2, [2,3], 1, [1,[2,3]]]

3

i need to process all the child nodes of [2,3] first and then process [2,3] and 1 and there’s no way for me to know that only 2,3 is associated with the [2,3] node.

Well, it is in this simple example but imagine [2,3] is called “A” and there are nodes 2,3,4. How would i know which of 1,2,3,4 are associated with “A” ? it could be 4 or 3,4 or 2,3,4 and so on, up to N.

Strangely i have implemented this, i just wanted AbstractTrees pretty printer, and when i implemented my DFS that’s the behaviour that i got, and i got it on my first try. however the behavior depends on what the kind of data the nodes have. i think that’s probably the difference.

regardless, i have the behavior i want now by a simple modification to the PostOrderDFS loop.

it’s now become of academic interest, because what i want to do seems very intuitive, but the “standard” DFS nomenclature doesn’t seem to include a version that does it that way.

4

So is what you want to always explore from the deepest leaf first? If so it seems like it would be more similar to a reversed bfs or something like that?

5

i’m a bit confused about why what i want isn’t simply depth first.

you can see that in the list generated by abstracttrees, that 1 is first.

however 2 and 3 are “deeper” in the tree, so why aren’t they first ?

the interesting thing is that the behavior is correctly documented by AbstractTrees. the documentation states:

Iterator to visit the nodes of a tree, guaranteeing that children will be visited before their parents.

and that’s what it does, strictly speaking. i’ve been investigating the nomenclature around DFS and sure enough post order DFS is what they are doing.

What i can’t find is the nomenclature to describe what i’m doing.

it’s definitely not a “reversed” BFS.

in what i will call purplishrock DFS :wink: you would visit 2,3 first then [2,3] and THEN either [2,3] order 1. the order their doesn’t matter because they are at the same level in the tree.

but visiting 1 before 2 & 3 makes no sense.

maybe it’s a “level ordered” DFS ?

6

Reversed BFS definitely does seem to be what you want, no?

julia> using AbstractTrees

julia> struct Node{T}
         data::T
         children::Vector{Node{T}}
       end

julia> Node(data::T) where T = Node(data, Node{T}[])
Node

julia> AbstractTrees.children(n::Node) = n.children

julia> AbstractTrees.printnode(io::IO, node::Node) = print(io, node.data)

julia> Base.show(io::IO, n::Node) = print(io, n.data)

julia> root = Node(1, [Node(2, [Node(5, [Node(9), Node(10)]), Node(6)]), Node(3)]);

julia> print_tree(root)
1
├─ 2
│  ├─ 5
│  │  ├─ 9
│  │  └─ 10
│  └─ 6
└─ 3

julia> reverse(collect(AbstractTrees.StatelessBFS(root)))
7-element Vector{Node{Int64}}:
 10
 9
 6
 5
 3
 2
 1
7

I don’t know, depends on what it is you want.

But based on what you are saying here it seems like a reversed bfs to me, though I’m not a 100 on exactly how they are defined tbh. In my head a dfs goes branch by branch, while bfs goes layer by layer. You are asking for something that goes layer by layer so it seems more like a kind of bfs, just that you do it in reverse compared to what a normal bfs would.

Found this which seems to be what you want, they call it reverse level order traversal. They do it with a bfs and a stack, just do bfs and push each item on stack, pop whole stack and print.

8

Not quite…

in that tree i would want

10
9
5
6
2
3
1

9

Hmm, okay. But then I don’t think I understand what it is you want again. You said that

and the only thing you changed was the order of 5 and 6 (same level) as well as 2 and 3 (same level).

What would you want in this case (1, [(2, [4, 5]), (3, [6, 7])])? On the phone so can’t draw nicely, but it should be a full binary tree with 3 levels.