TreePlot doesn't respect order of subtrees

[roland-KA]

I tried to plot some binary trees with TreePlot and noticed that sometimes the left and right subtrees are plotted in the correct order and sometimes not.

Here is a MWE for the issue:

using Plots
using GraphRecipes
using AbstractTrees

t = [1,2,4,8,9,5,10,11,3,6,12,13,7,14,15]

function subtree(tree::Vector{Int}, left::Bool)
    len = (length(tree) - 1) ÷ 2
    if len == 1 
        return(left ? tree[2] : tree[3])
    else
        offset = left ? 0 : len
        return(tree[2+offset:len+1+offset])  
    end
end

AbstractTrees.children(node::Vector{Int}) = (subtree(node, true), subtree(node, false))
AbstractTrees.printnode(io::IO, node::Vector{Int}) = print(io, "Node\n", node[1])
AbstractTrees.printnode(io::IO, node::Int) = print(io, "Leaf\n", node)

plot(TreePlot(t), method = :tree, nodeshape = :rect, nodesize = 0.3, size = (900,900))

This should plot a tree with the nodes numbered (in breadth-first order) from 1 ... 15: 1 2 - 3 4 - 5 -- 6 - 7 8 -9 -- 10 - 11 -- 12 - 13 -- 14 - 15

But actually I get this:

So the following pairs are in wrong order: (2,3) (6,7) (4,5) (8,9) (12,13) But others are correct like: (14,15) (10,11)

If I print the tree in text format using print_tree all subtrees are in the correct order (print_tree prints the left subtree first and then the right subtree).

Node
1
├─ Node
│  2
│  ├─ Node
│  │  4
│  │  ├─ Leaf
│  │  │  8
│  │  └─ Leaf
│  │     9
│  └─ Node
│     5
│     ├─ Leaf
│     │  10
│     └─ Leaf
│        11
└─ Node
   3
   ├─ Node
   │  6
   │  ├─ Leaf
   │  │  12
   │  └─ Leaf
   │     13
   └─ Node
      7
      ├─ Leaf
      │  14
      └─ Leaf
         15

Interestingly a tree with one level less gets plotted correctly:

[roland-KA]

And another interesting observation: Each call to plot(TreePlot(...)) produces (using the same arguments) a different tree. Each one with more or less errors. This is e.g. another figure plotted with the code above using exactly the same arguments:

Here we have issues with the pairs: (4, 5), (10, 11), (12, 13), (14, 15).

[roland-KA]

In the meantime I've carried out a few more tests: If the Buchheim algorithm for tree layout is used (method = :buchheim), then the trees are plotted correctly. So the issue described above is only related to the layout algorithm (method = :tree).

This layout algorithm has also other issues. The argument root, which specifies the orientation of the tree layout (top, left, right or bottom) is mostly ignored by this algorithm whearas with method = :buchheim everything works fine.