node_number_at_depth broken for binary trees

[mwageringel]

sage: ascii_art(BinaryTrees(3).list())
[ o    , o  ,   o  ,   o,     o ]
[  \      \    / \    /      /  ]
[   o      o  o   o  o      o   ]
[    \    /           \    /    ]
[     o  o             o  o     ]
sage: [t.node_number_at_depth(0) for t in BinaryTrees(3)]  # correct
[1, 1, 1, 1, 1]
sage: [t.node_number_at_depth(1) for t in BinaryTrees(3)]  # expected [1, 1, 2, 1, 1]
[2, 2, 2, 2, 2]
sage: [t.node_number_at_depth(2) for t in BinaryTrees(3)]  # expected [1, 1, 0, 1, 1]
[2, 2, 4, 2, 2]

This comes from the fact that the empty tree thinks it has 1 node at depth 0:

sage: T = BinaryTree()
sage: T
.
sage: T.is_empty()
True
sage: T.node_number_at_depth(0)
1

CC: @tscrim @jm58660 @darijgr

Component: combinatorics

Author: Travis Scrimshaw

Branch/Commit: aaa0581

Reviewer: Markus Wageringel

Issue created by migration from https://trac.sagemath.org/ticket/29134

[fchapoton]

comment:1

For compactness, the usual ascii_art plot does not display the leaves, which nevertheless are nodes.

sage: ascii_art([t.to_full() for t in BinaryTrees(3)])
[   _o__       ,   __o___     ,     __o__    ,      __o___  ,        _o__   ]
[  /    \         /      \         /     \         /      \         /    \  ]
[ o     _o_      o       _o_      o       o      _o_       o      _o_     o ]
[      /   \            /   \    / \     / \    /   \            /   \      ]
[     o     o          o     o  o   o   o   o  o     o          o     o     ]
[          / \        / \                           / \        / \          ]
[         o   o      o   o                         o   o      o   o         ]

[fchapoton]

comment:2

I therefore suggest to close as invalid. All the conventions are clearly explained in the documentation.

[mwageringel]

comment:3

Replying to @fchapoton:

For compactness, the usual ascii_art plot does not display the leaves, which nevertheless are nodes.

Indeed, that explains the output I got. It is still a bit confusing that node_number_at_depth counts nodes including leaves, while node_number does not include the leaves.

sage: [t.node_number() for t in BinaryTrees(3)]
[3, 3, 3, 3, 3]

In my opinion, there is an inconsistency that should be fixed.

The documentation is not that clear about this. If anything, I am inclined to interpret it as saying that leaves are not considered nodes in binary trees:

    Binary trees contain nodes and leaves, where each node has two
    children while each leaf has no children. The number of leaves
    of a binary tree always equals the number of nodes plus `1`.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: aaa0581

[tscrim]

Branch: public/combinat/fix_node_number_at_depth_empty_tree-29134

[tscrim]

comment:4

I think it is slightly misleading to say ascii_art does not display the leaves. I would consider there to be two distinct sets of objects:

1 - binary trees with n nodes and
2 - full binary trees with n internal nodes.

There is a definite inconsistency here between node_number and node_number_at_depth. The problem is this corner case:

sage: T = BinaryTrees(3)[3]
sage: Tp = T[1]
sage: Tp
.
sage: Tp.is_empty()
True
sage: Tp.node_number_at_depth(0)
1

In particular, it says an empty tree has 1 node, which is wrong. This branch fixes this.

---

New commits:

aaa0581

Fixing node_number_at_depth for empty trees.

[mwageringel]

comment:5

Thanks for fixing this so quickly. It works exactly as I expect.

Frédéric, if you agree, I think this can be set to positive.

[mwageringel]

Reviewer: Markus Wageringel

[fchapoton]

comment:6

do whatever you want, I have no time

[mwageringel]

comment:7

Ok, no problem.

[vbraun]

Changed branch from public/combinat/fix_node_number_at_depth_empty_tree-29134 to aaa0581