# Binary trees¶

This module deals with binary trees as mathematical (in particular immmutable) objects.

Note

If you need the data-structure for example to represent sets or hash tables with AVL trees, you should have a look at sage.misc.sagex_ds.

AUTHORS:

• Florent Hivert (2010-2011): initial implementation.
class sage.combinat.binary_tree.BinaryTree(parent, children=None, check=True)

The class of binary trees

Binary trees here mean ordered (a.k.a. plane) binary trees, meaning that the children of each node are ordered.

INPUT:

• childrenNone (default) or a list, tuple or iterable of length 2 of binary trees or convertible objects. This corresponds to the standard recursive definition of a binary tree as either a leaf or a pair of binary trees. Syntactic sugar allows leaving out all but the outermost calls of the BinaryTree() constructor, so that, e. g., BinaryTree([BinaryTree(None),BinaryTree(None)]) can be simplified to BinaryTree([None,None]). It is also allowed to abbreviate [None, None] by [].
• check – (default to True) whether check for binary should be performed or not.

EXAMPLES:

sage: BinaryTree()
.
sage: BinaryTree(None)
.
sage: BinaryTree([])
[., .]
sage: BinaryTree([None, None])
[., .]
sage: BinaryTree([None, []])
[., [., .]]
sage: BinaryTree([[], None])
[[., .], .]
sage: BinaryTree("[[], .]")
[[., .], .]

sage: BinaryTree([[], None, []])
Traceback (most recent call last):
...
ValueError: this is not a binary tree


TESTS:

sage: t1 = BinaryTree([[None, [[],[[], None]]],[[],[]]])
sage: t2 = BinaryTree([[[],[]],[]])
sage: with t1.clone() as t1c:
...       t1c[1,1,1] = t2
sage: t1 == t1c
False

as_ordered_tree(*args, **kwds)

Return the same tree seen as an ordered tree. By default, leaves are transformed into actual nodes.

EXAMPLES:

sage: bt = BinaryTree([]); bt
[., .]
sage: bt.as_ordered_tree()
[[], []]
sage: bt.as_ordered_tree(with_leaves = False)
[]
sage: bt = bt.canonical_labelling(); bt
1[., .]
sage: bt.as_ordered_tree()
1[None[], None[]]
sage: bt.as_ordered_tree(with_leaves=False)
1[]

canonical_labelling(shift=1)

Return a labelled version of self.

The actual canonical labelling is currently unspecified. However, it is guaranteed to have labels in $$1...n$$ where $$n$$ is the number of nodes of the tree. Moreover, two (unlabelled) trees compare as equal if and only if their canonical labelled trees compare as equal.

EXAMPLES:

sage: BinaryTree().canonical_labelling()
.
sage: BinaryTree([]).canonical_labelling()
1[., .]
sage: BinaryTree([[[], [[], None]], [[], []]]).canonical_labelling()
5[2[1[., .], 4[3[., .], .]], 7[6[., .], 8[., .]]]

canopee()

Return the canopee of self

The canopee of a non empty binary tree $$T$$ with $$n$$ internal nodes is the list $$l$$ of $$0$$ and $$1$$ of length $$n-1$$ obtained by going along the leaves of $$T$$ from left to right except the two extremal ones, writing $$0$$ if the leaf is a right leaf and $$1$$ if the leaf is a left leaf.

EXAMPLES:

sage: BinaryTree([]).canopee()
[]
sage: BinaryTree([None, []]).canopee()
[1]
sage: BinaryTree([[], None]).canopee()
[0]
sage: BinaryTree([[], []]).canopee()
[0, 1]
sage: BinaryTree([[[], [[], None]], [[], []]]).canopee()
[0, 1, 0, 0, 1, 0, 1]


The number of pairs $$(t_1, t_2)$$ of binary trees of size $$n$$ such that the canopee of $$t_1$$ is the complementary of the canopee of $$t_2$$ is also the number of Baxter permutations (see [DG], see also OEIS sequence A001181). We check this in small cases:

sage: [len([(u,v) for u in BinaryTrees(n) for v in BinaryTrees(n)
...       if map(lambda x:1-x, u.canopee()) == v.canopee()])
...    for n in range(1, 5)]
[1, 2, 6, 22]


Here is a less trivial implementation of this:

sage: from sage.sets.finite_set_map_cy import fibers
sage: from sage.misc.all import attrcall
sage: def baxter(n):
...      f = fibers(lambda t: tuple(t.canopee()),
...                   BinaryTrees(n))
...      return sum(len(f[i])*len(f[tuple(1-x for x in i)])
...                 for i in f)
sage: [baxter(n) for n in range(1, 7)]
[1, 2, 6, 22, 92, 422]


TESTS:

sage: t = BinaryTree().canopee()
Traceback (most recent call last):
...
ValueError: canopee is only defined for non empty binary trees


REFERENCES:

 [DG] S. Dulucq and O, Guibert. Mots de piles, tableaux standards et permutations de Baxter, proceedings of Formal Power Series and Algebraic Combinatorics, 1994.
check()

Checks that self is a binary tree

EXAMPLES:

sage: BinaryTree([[], []])     # indirect doctest
[[., .], [., .]]
sage: BinaryTree([[], [], []]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree
sage: BinaryTree([[]])         # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree

graph()

Convert self to a digraph

EXAMPLE:

sage: t1 = BinaryTree([[], None])
sage: t1.graph()
Digraph on 5 vertices

sage: t1 = BinaryTree([[], [[], None]])
sage: t1.graph()
Digraph on 9 vertices
sage: t1.graph().edges()
[(0, 1, None), (0, 4, None), (1, 2, None), (1, 3, None), (4, 5, None), (4, 8, None), (5, 6, None), (5, 7, None)]

is_empty()

Return whether self is empty.

EXAMPLES:

sage: BinaryTree().is_empty()
True
sage: BinaryTree([]).is_empty()
False
sage: BinaryTree([[], None]).is_empty()
False

left_border_symmetry(*args, **kwds)

Return the tree where a symmetry has been applied recursively on all left borders. If a tree is made of three trees $$[T_1, T_2, T_3]$$ on its left border, it becomes $$[T_3', T_2', T_1']$$ where same symmetry has been applied to $$T_1, T_2, T_3$$.

EXAMPLES:

sage: BinaryTree().left_border_symmetry()
.
sage: BinaryTree([]).left_border_symmetry()
[., .]
sage: BinaryTree([[None,[]],None]).left_border_symmetry()
[[., .], [., .]]
sage: BinaryTree([[None,[None,[]]],None]).left_border_symmetry()
[[., .], [., [., .]]]
sage: bt = BinaryTree([[None,[None,[]]],None]).canonical_labelling()
sage: bt
4[1[., 2[., 3[., .]]], .]
sage: bt.left_border_symmetry()
1[4[., .], 2[., 3[., .]]]

left_right_symmetry(*args, **kwds)

Return the left-right symmetrized tree of self.

EXAMPLES:

sage: BinaryTree().left_right_symmetry()
.
sage: BinaryTree([]).left_right_symmetry()
[., .]
sage: BinaryTree([[],None]).left_right_symmetry()
[., [., .]]
sage: BinaryTree([[None, []],None]).left_right_symmetry()
[., [[., .], .]]

make_leaf()

Modify self so that it became a leaf

Note

self must be in a mutable state.

make_node

EXAMPLES:

sage: t = BinaryTree([None, None])
sage: t.make_leaf()
Traceback (most recent call last):
...
sage: with t.clone() as t1:
...    t1.make_leaf()
sage: t, t1
([., .], .)

make_node(child_list=[None, None])

Modify self so that it becomes a node with children childlist

INPUT:

• child_list – a pair of binary trees (or objects convertible to)

Note

self must be in a mutable state.

make_leaf

EXAMPLES:

sage: t = BinaryTree()
sage: t.make_node([None, None])
Traceback (most recent call last):
...
sage: with t.clone() as t1:
...    t1.make_node([None, None])
sage: t, t1
(., [., .])
sage: with t.clone() as t:
...    t.make_node([BinaryTree(), BinaryTree(), BinaryTree([])])
Traceback (most recent call last):
...
ValueError: the list must have length 2
sage: with t1.clone() as t2:
...    t2.make_node([t1, t1])
sage: with t2.clone() as t3:
...    t3.make_node([t1, t2])
sage: t1, t2, t3
([., .], [[., .], [., .]], [[., .], [[., .], [., .]]])

show()

TESTS:

sage: t1 = BinaryTree([[], [[], None]])
sage: t1.show()

to_132_avoiding_permutation(*args, **kwds)

Return a 132-avoiding permutation corresponding to the binary tree.

The linear extensions of a binary tree form an interval of the weak order called the sylester class of the tree. This permutation is the maximal element of this sylvester class.

EXAMPLES:

sage: bt = BinaryTree([[],[]])
sage: bt.to_132_avoiding_permutation()
[3, 1, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_132_avoiding_permutation()
[8, 6, 7, 3, 4, 1, 2, 5]


TESTS:

sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True

to_312_avoiding_permutation(*args, **kwds)

Return a 312-avoiding permutation corresponding to the binary tree.

The linear extensions of a binary tree form an interval of the weak order called the sylester class of the tree. This permutation is the minimal element of this sylvester class.

EXAMPLES:

sage: bt = BinaryTree([[],[]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 4, 2, 6, 8, 7, 5]


TESTS:

sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True

to_dyck_word(*args, **kwds)

INPUT:

• usemap – a string, either 1L0R, 1R0L, L1R0, R1L0

Return the Dyck word associated with self using the given map.

The bijection is defined recursively as follows:

• a leaf is associated to the empty Dyck Word
• a tree with children $$l,r$$ is associated with the Dyck word described by usemap where $$L$$ and $$R$$ are respectively the Dyck words associated with the $$l$$ and $$r$$.

EXAMPLES:

sage: BinaryTree().to_dyck_word()
[]
sage: BinaryTree([]).to_dyck_word()
[1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word()
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word()
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("1R0L")
[1, 0, 1, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("L1R0")
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R1L0")
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R10L")
Traceback (most recent call last):
...
ValueError: R10L is not a correct map


TESTS:

sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_dyck_word().to_binary_tree()
True
sage: bt == bt.to_dyck_word("1R0L").to_binary_tree("1R0L")
True
sage: bt == bt.to_dyck_word("L1R0").to_binary_tree("L1R0")
True
sage: bt == bt.to_dyck_word("R1L0").to_binary_tree("R1L0")
True

to_dyck_word_tamari(*args, **kwds)

Return the Dyck word associated with self in consistency with the Tamari order on dyck words and binary trees.

The bijection is defined recursively as follows:

• a leaf is associated with an empty Dyck word
• a tree with children $$l,r$$ is associated with the Dyck word $$T(l) 1 T(r) 0$$

EXAMPLES:

sage: BinaryTree().to_dyck_word_tamari()
[]
sage: BinaryTree([]).to_dyck_word_tamari()
[1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word_tamari()
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word_tamari()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]

to_ordered_tree_left_branch(*args, **kwds)

Return an ordered tree of size $$n+1$$ by the following recursive rule:

• if $$x$$ is the left child of $$y$$, $$x$$ becomes the left brother of $$y$$
• if $$x$$ is the right child of $$y$$, $$x$$ becomes the last child of $$y$$

EXAMPLES:

sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_left_branch()
[[], [[]]]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_left_branch()
[[], [[], []], [[], [[]]]]

to_ordered_tree_right_branch(*args, **kwds)

Return an ordered tree of size n+1 by the following recursive rule:

• if $$x$$ is the right child of $$y$$, $$x$$ becomes the right brother of $$y$$
• if $$x$$ is the left child of $$y$$, $$x$$ becomes the first child of $$y$$

EXAMPLES:

sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_right_branch()
[[[]], []]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_right_branch()
[[[[]], [[]]], [[]], []]

to_poset(*args, **kwds)

Return the poset obtained by interpreting the tree as a hasse diagram.

The default orientation is from leaves to root but you can pass root_to_leaf=True to obtain the inverse orientation.

Leafs are ignored by default but can set with_leaves to True to obtain the poset of the complete tree.

INPUT:

• with_leaves – boolean, true if leaves should be added to the poset
• root_to_leaf – boolean, true if the poset orientation should be from root to leaves. It is false by default.

EXAMPLES:

sage: bt = BinaryTree([])
sage: bt.to_poset()
Finite poset containing 1 elements
sage: bt.to_poset(with_leaves=True)
Finite poset containing 3 elements
sage: bt.to_poset(with_leaves=True).cover_relations()
[[0, 2], [1, 2]]
sage: bt = BinaryTree([])
sage: bt.to_poset(with_leaves=True,root_to_leaf=True).cover_relations()
[[0, 1], [0, 2]]


If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:

sage: bt = BinaryTree([[],[None,[]]]).canonical_labelling()
sage: bt
2[1[., .], 3[., 4[., .]]]
sage: bt.to_poset().cover_relations()
[[4, 3], [3, 2], [1, 2]]

to_undirected_graph(*args, **kwds)

Return the undirected graph obtained from the tree nodes and edges. Leafs are ignored by default but can set with_leaves to True to obtain the graph of the complete tree.

EXAMPLES:

sage: bt = BinaryTree([])
sage: bt.to_undirected_graph()
Graph on 1 vertex
sage: bt.to_undirected_graph(with_leaves=True)
Graph on 3 vertices


If the tree is labelled, we use its labelling to label the graph. Otherwise, we use the graph canonical labelling which means that two different trees can have the same graph.

EXAMPLES:

sage: bt = BinaryTree([[],[None,[]]])
sage: bt.canonical_labelling()
2[1[., .], 3[., 4[., .]]]
sage: bt.canonical_labelling().to_undirected_graph().edges()
[(1, 2, None), (2, 3, None), (3, 4, None)]
sage: bt.to_undirected_graph().edges()
[(0, 3, None), (1, 2, None), (2, 3, None)]
sage: bt.canonical_labelling().to_undirected_graph() == bt.to_undirected_graph()
False
sage: BinaryTree([[],[]]).to_undirected_graph() == BinaryTree([[[],None],None]).to_undirected_graph()
True

class sage.combinat.binary_tree.BinaryTrees

Factory for binary trees.

INPUT:

• size – (optional) an integer

OUPUT:

• the set of all binary trees (of the given size if specified)

EXAMPLES:

sage: BinaryTrees()
Binary trees

sage: BinaryTrees(2)
Binary trees of size 2


Note

this in a factory class whose constructor returns instances of subclasses.

Note

the fact that OrderedTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.

leaf()

Return a left tree with self as parent.

EXAMPLES:

sage: BinaryTrees().leaf()
.


TEST:

sage: (BinaryTrees().leaf() is
...    sage.combinat.binary_tree.BinaryTrees_all().leaf())
True

class sage.combinat.binary_tree.BinaryTrees_all

TESTS:

sage: from sage.combinat.binary_tree import BinaryTrees_all
sage: B = BinaryTrees_all()
sage: B.cardinality()
+Infinity

sage: it = iter(B)
sage: (it.next(), it.next(), it.next(), it.next(), it.next())
(., [., .], [., [., .]], [[., .], .], [., [., [., .]]])
sage: it.next().parent()
Binary trees
sage: B([])
[., .]

sage: B is BinaryTrees_all()
True
sage: TestSuite(B).run()

Element

alias of BinaryTree

labelled_trees()

Return the set of labelled trees associated to self

EXAMPLES:

sage: BinaryTrees().labelled_trees()
Labelled binary trees

unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: BinaryTrees().unlabelled_trees()
Binary trees

class sage.combinat.binary_tree.BinaryTrees_size(size)

The enumerated sets of binary trees of given size

TESTS:

sage: from sage.combinat.binary_tree import BinaryTrees_size
sage: for i in range(6): TestSuite(BinaryTrees_size(i)).run()

cardinality()

The cardinality of self

This is a Catalan number.

TESTS:

sage: BinaryTrees(0).cardinality()
1
sage: BinaryTrees(5).cardinality()
42

element_class()

TESTS:

sage: S = BinaryTrees(3)
sage: S.element_class
<class 'sage.combinat.binary_tree.BinaryTrees_all_with_category.element_class'>
sage: S.first().__class__ == BinaryTrees().first().__class__
True

class sage.combinat.binary_tree.LabelledBinaryTree(parent, children, label=None, check=True)

The class of labelled binary tree

EXAMPLE:

sage: LBT = LabelledBinaryTree
sage: t1 = LBT([[LBT([], label=2), None], None], label=4); t1
4[None[2[., .], .], .]

binary_search_insert(letter)

Insert a letter in a binary search tree

INPUT:

• letter – any object comparable with the label of self

Note

self is supposed to be a binary search tree. No check is performed.

EXAMPLES:

sage: LBT = LabelledBinaryTree
sage: LBT(None).binary_search_insert(3)
3[., .]
sage: LBT([], label = 1).binary_search_insert(3)
1[., 3[., .]]
sage: LBT([], label = 3).binary_search_insert(1)
3[1[., .], .]
sage: res = LBT(None)
sage: for i in [3,1,5,2,4,6]:
...       res = res.binary_search_insert(i)
sage: res
3[1[., 2[., .]], 5[4[., .], 6[., .]]]

class sage.combinat.binary_tree.LabelledBinaryTrees(category=None)

This is a parent stub to serve as a factory class for trees with various labels constraints

Element

alias of LabelledBinaryTree

labelled_trees()

Return the set of labelled trees associated to self

EXAMPLES:

sage: LabelledBinaryTrees().labelled_trees()
Labelled binary trees

unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: LabelledBinaryTrees().unlabelled_trees()
Binary trees


This is used to compute the shape:

sage: t = LabelledBinaryTrees().an_element().shape(); t
[[[., .], [., .]], [[., .], [., .]]]
sage: t.parent()
Binary trees


TESTS:

sage: t = LabelledBinaryTrees().an_element()
sage: t.canonical_labelling()
4[2[1[., .], 3[., .]], 6[5[., .], 7[., .]]]


#### Previous topic

Ordered Rooted Trees

#### Next topic

Similarity class types of matrices with entries in a finite field