# Ordered Rooted Trees¶

AUTHORS:

• Florent Hivert (2010-2011): initial revision
• Frederic Chapoton (2010): contributed some methods
class sage.combinat.ordered_tree.LabelledOrderedTree(parent, children, label=None, check=True)

Labelled ordered trees.

A labelled ordered tree is an ordered tree with a label attached at each node.

INPUT:

• children – a list or tuple or more generally any iterable

of trees or object convertible to trees

• label – any Sage object default to None

EXAMPLES:

sage: x = LabelledOrderedTree([], label = 3); x
3[]
sage: LabelledOrderedTree([x, x, x], label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree((x, x, x), label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree([[],[[], []]], label = 3)
3[None[], None[None[], None[]]]

class sage.combinat.ordered_tree.LabelledOrderedTrees(category=None)

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

EXAMPLES:

sage: LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
sage: x = LOT([], label = 3); x
3[]
sage: x.parent() is LOT
True
sage: y = LOT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LOT
True

Element

alias of LabelledOrderedTree

cardinality()

Return the cardinality of $$self$$.

EXAMPLE:

sage: LabelledOrderedTrees().cardinality()
+Infinity

labelled_trees()

Return the set of labelled trees associated to self.

This is precisely self, because self already is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().labelled_trees()
Labelled ordered trees
sage: LOT = LabelledOrderedTrees()
sage: x = LOT([], label = 3)
sage: y = LOT([x, x, x], label = 2)
sage: y.canonical_labelling()
1[2[], 3[], 4[]]

unlabelled_trees()

Return the set of unlabelled trees associated to self.

This is the set of ordered trees, since self is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().unlabelled_trees()
Ordered trees

class sage.combinat.ordered_tree.OrderedTree(parent=None, children=[], check=True)

The class of (ordered rooted) trees.

An ordered tree is constructed from a node, called the root, on which one has grafted a possibly empty list of trees. There is a total order on the children of a node which is given by the order of the elements in the list. Note that there is no empty ordered tree (so the smallest ordered tree consists of just one node).

INPUT:

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree. Alternatively a string is also accepted. The syntax is the same as for printing: children are grouped by square brackets.

EXAMPLES:

sage: x = OrderedTree([])
sage: x1 = OrderedTree([x,x])
sage: x2 = OrderedTree([[],[]])
sage: x1 == x2
True
sage: tt1 = OrderedTree([x,x1,x2])
sage: tt2 = OrderedTree([[], [[], []], x2])
sage: tt1 == tt2
True

sage: OrderedTree([]) == OrderedTree()
True


TESTS:

sage: x1.__hash__() == x2.__hash__()
True
sage: tt1.__hash__() == tt2.__hash__()
True


Trees are usually immutable. However they inherit from sage.structure.list_clone.ClonableList, so that they can be modified using the clone protocol. Let us now see what this means.

Trying to modify a non-mutable tree raises an error:

sage: tt1[1] = tt2
Traceback (most recent call last):
...


Here is the correct way to do it:

sage: with tt2.clone() as tt2:
....:     tt2[1] = tt1
sage: tt2
[[], [[], [[], []], [[], []]], [[], []]]


It is also possible to append a child to a tree:

sage: with tt2.clone() as tt3:
....:     tt3.append(OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [[], []], []]


Or to insert a child in a tree:

sage: with tt2.clone() as tt3:
....:     tt3.insert(2, OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [], [[], []]]


We check that tt1 is not modified and that everything is correct with respect to equality:

sage: tt1
[[], [[], []], [[], []]]
sage: tt1 == tt2
False
sage: tt1.__hash__() == tt2.__hash__()
False


TESTS:

sage: tt1bis = OrderedTree(tt1)
sage: with tt1.clone() as tt1:
....:     tt1[1] = tt1bis
sage: tt1
[[], [[], [[], []], [[], []]], [[], []]]
sage: tt1 == tt2
True
sage: tt1.__hash__() == tt2.__hash__()
True
sage: len(tt1)
3
sage: tt1[2]
[[], []]
sage: tt1[3]
Traceback (most recent call last):
...
IndexError: list index out of range
sage: tt1[1:2]
[[[], [[], []], [[], []]]]


Various tests involving construction, equality and hashing:

sage: OrderedTree() == OrderedTree()
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1 == t2
True
sage: t2 = OrderedTree(t1)
sage: t1 == t2
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[[]],[]])
sage: t1 == t2
False

sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1.__hash__() == t2.__hash__()
True
sage: t2 = OrderedTree([[[]],[]])
sage: t1.__hash__() == t2.__hash__()
False
sage: OrderedTree().__hash__() == OrderedTree([]).__hash__()
True
sage: tt1 = OrderedTree([t1,t2,t1])
sage: tt2 = OrderedTree([t1, [[[]],[]], t1])
sage: tt1.__hash__() == tt2.__hash__()
True


Check that the hash value is correctly updated after modification:

sage: with tt2.clone() as tt2:
....:     tt2[1,1] = tt1
sage: tt1.__hash__() == tt2.__hash__()
False

is_empty()

Return if self is the empty tree.

For ordered trees, this always returns False.

Note

this is different from bool(t) which returns whether t has some child or not.

EXAMPLES:

sage: t = OrderedTrees(4)([[],[[]]])
sage: t.is_empty()
False
sage: bool(t)
True

left_right_symmetry()

Return the symmetric tree of self

EXAMPLES:

sage: T = OrderedTree([[],[[]]])
sage: T.left_right_symmetry()
[[[]], []]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.left_right_symmetry()
[[[[]], []], [[], []], []]

to_binary_tree_left_branch()

Return a binary tree of size $$n-1$$ (where $$n$$ is the size of $$t$$, and where $$t$$ is self) obtained from $$t$$ by the following recursive rule:

• if $$x$$ is the left brother of $$y$$ in $$t$$, then $$x$$ becomes the left child of $$y$$;
• if $$x$$ is the last child of $$y$$ in $$t$$, then $$x$$ becomes the right child of $$y$$,

and removing the root of $$t$$.

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_left_branch()
[[., .], .]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_left_branch()
[[[., .], [[., .], .]], [[., .], [., .]]]


TESTS:

sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True

to_binary_tree_right_branch()

Return a binary tree of size $$n-1$$ (where $$n$$ is the size of $$t$$, and where $$t$$ is self) obtained from $$t$$ by the following recursive rule:

• if $$x$$ is the right brother of $$y$$ in $$t$$, thenx becomes the right child of $$y$$;
• if $$x$$ is the first child of $$y$$ in $$t$$, then $$x$$ becomes the left child of $$y$$,

and removing the root of $$t$$.

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_right_branch()
[., [., .]]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_right_branch()
[., [[., [., .]], [[., [[., .], .]], .]]]


TESTS:

sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True

to_dyck_word()

Return the Dyck path corresponding to self where the maximal height of the Dyck path is the depth of self .

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_dyck_word()
[1, 0, 1, 0]
sage: T = OrderedTree([[],[[]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 0]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]

to_poset(root_to_leaf=False)

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.

INPUT:

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

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_poset()
Finite poset containing 1 elements
sage: p = OrderedTree([[[]],[],[]]).to_poset()
sage: p.cover_relations()
[[0, 4], [1, 4], [2, 3], [3, 4]]
sage: p = OrderedTree([[[]],[],[]]).to_poset(root_to_leaf=True)
sage: p.cover_relations()
[[0, 2], [0, 3], [0, 4], [4, 1]]


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

sage: t = OrderedTree([[[]],[],[]]).canonical_labelling()
sage: t
1[2[3[]], 4[], 5[]]
sage: t.to_poset().cover_relations()
[[5, 1], [4, 1], [3, 2], [2, 1]]

to_undirected_graph()

Return the undirected graph obtained from the tree nodes and edges.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_undirected_graph()
Graph on 1 vertex
sage: t = OrderedTree([[[]],[],[]])
sage: t.to_undirected_graph()
Graph on 5 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: t = OrderedTree([[[]],[],[]])
sage: t.canonical_labelling().to_undirected_graph()
Graph on 5 vertices
sage: t.canonical_labelling().to_undirected_graph() == t.to_undirected_graph()
False
sage: OrderedTree([[],[]]).to_undirected_graph() == OrderedTree([[[]]]).to_undirected_graph()
True
sage: OrderedTree([[],[],[]]).to_undirected_graph() == OrderedTree([[[[]]]]).to_undirected_graph()
False

class sage.combinat.ordered_tree.OrderedTrees

Factory for ordered trees

INPUT:

• size – (optional) an integer

OUPUT:

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

EXAMPLES:

sage: OrderedTrees()
Ordered trees

sage: OrderedTrees(2)
Ordered trees of size 2


Note

this is 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 leaf tree with self as parent

EXAMPLES:

sage: OrderedTrees().leaf()
[]


TEST:

sage: (OrderedTrees().leaf() is
....:     sage.combinat.ordered_tree.OrderedTrees_all().leaf())
True

class sage.combinat.ordered_tree.OrderedTrees_all

The set of all ordered trees.

EXAMPLES:

sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity

Element

alias of OrderedTree

labelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: OrderedTrees().labelled_trees()
Labelled ordered trees

unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: OrderedTrees().unlabelled_trees()
Ordered trees

class sage.combinat.ordered_tree.OrderedTrees_size(size)

The enumerated sets of binary trees of a given size

EXAMPLES:

sage: S = OrderedTrees(3); S
Ordered trees of size 3
sage: S.cardinality()
2
sage: S.list()
[[[], []], [[[]]]]

cardinality()

The cardinality of self

This is a Catalan number.

TESTS:

sage: OrderedTrees(0).cardinality()
0
sage: OrderedTrees(1).cardinality()
1
sage: OrderedTrees(6).cardinality()
42

element_class()

The class of the element of self

EXAMPLES:

sage: from sage.combinat.ordered_tree import OrderedTrees_size, OrderedTrees_all
sage: S = OrderedTrees_size(3)
sage: S.element_class is OrderedTrees().element_class
True
sage: S.first().__class__ == OrderedTrees_all().first().__class__
True


#### Previous topic

Abstract Recursive Trees

Binary Trees.