# AbstractTrees needs one more kind of DFS?
**URL:** https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468
**Category:** General Usage
**Created:** [January 12, 2022, 6:08am UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468 "2022-01-12T06:08:59Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@purplishrock](https://discourse.julialang.org/u/purplishrock)
#### Post date: [January 12, 2022, 6:08am UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/1 "2022-01-12T06:08:59Z")
Here is what a PostOrderDFS does
```julia
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…
---
### Author:  [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)
#### Post date: [January 12, 2022, 9:16am UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/2 "2022-01-12T09:16:32Z")
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]]]`
---
### Author:  [@purplishrock](https://discourse.julialang.org/u/purplishrock)
#### Post date: [January 12, 2022, 3:59pm UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/3 "2022-01-12T15:59:55Z")
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.
---
### Author:  [@albheim](https://discourse.julialang.org/u/albheim)
#### Post date: [January 12, 2022, 4:45pm UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/4 "2022-01-12T16:45:50Z")
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?
---
### Author:  [@purplishrock](https://discourse.julialang.org/u/purplishrock)
#### Post date: [January 12, 2022, 5:20pm UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/5 "2022-01-12T17:20:14Z")
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 😉 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 ?
---
### Author:  [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)
#### Post date: [January 12, 2022, 7:00pm UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/6 "2022-01-12T19:00:05Z")
Reversed BFS definitely does seem to be what you want, no?
```julia
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
```
---
### Author:  [@albheim](https://discourse.julialang.org/u/albheim)
#### Post date: [January 12, 2022, 7:21pm UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/7 "2022-01-12T19:21:37Z")
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](https://www.techiedelight.com/reverse-level-order-traversal-binary-tree/) 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.
---
### Author:  [@purplishrock](https://discourse.julialang.org/u/purplishrock)
#### Post date: [January 13, 2022, 2:44am UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/8 "2022-01-13T02:44:19Z")
Not quite…
in that tree i would want
10
9
5
6
2
3
1
---
### Author:  [@albheim](https://discourse.julialang.org/u/albheim)
#### Post date: [January 13, 2022, 7:47am UTC](https://discourse.julialang.org/t/abstracttrees-needs-one-more-kind-of-dfs/74468/9 "2022-01-13T07:47:39Z")
Hmm, okay. But then I don’t think I understand what it is you want again. You said that
> [@purplishrock](#):
>
> the order their doesn’t matter because they are at the same level in the tree
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.