Ordered rooted tree

Ordered rooted tree:

An ordered rooted tree is a rooted tree where the children at each internal vertex are ordered. Ordered rooted trees dare drawn . So than the children of each internal vertex are shown in order from left to right. In an ordered binary tree (which is called just binary tree), if an internal vertex has two children, the first child is called left child and the 2^nd child is called right child.

The tree rooted at let child of a vertex is called the left sub tree of this vertex.The tree rooted at right child of a vertices is called the right sub tree of this vertex.

Ordered rooted tree.

Right subtree                                                                                                             left subtree

Theorem: A full m-any tree ei internal vertices contain n=mi+1 vertices.

Proof: Every vertices except the root is the child of an internal vertices. Since each of the I internal vertices has m child . Then there are mi vertices in the tree other than root.\Therefore, the tree contains n=mi+1

Theorem: A fall m-any tree with

1.      N vertices have i=  internal vertices and L =  leaves.

2.      I internal vertices has n = mi+1 vertices and  L = (m-1)I 1 leaves.

3.      L leaves has n =  vertices and I =   internal vertices.

Proof: let n represents eis the number of vertices   I is the number of internal vertices and I is the number of leaves. The theorem can be proved by using the equality n=mi+1 with n= l+I . we know a full m-any tree with I internal vertices contain n = mi+1 vertices

i.e n = mi + 1….(1)

also n = l+i………….(2)

Which also tree because each vetex is either a leaf or an internal vertex. Now from (1) 

mi = n-1

Þ I =

i.e n vertices has I =  internal vetices.

Now from (2) l = n-i

Þ      l = n -

Þ      l =

Þ      l =

Therefore n vertices has  l =    leaves.

(2) Proof: In a full m-any tre with I internal vertices, every vetieces except the root is the child of an internal vertices since each of I internal vertices has m children.

Then there are mii vertices in the tree other than root. Thus the etree contan n = mi + 1 vertices If the tree has l leaves , then n = l + i

                                    Therefore, l + i= mi + 1

                                    Þ   l = mi – i + 1

                                    Þ l = (m-1) i + 1

Hence the tree has l= (m-1) i + 1 leaves.

(3) Proof: let the tree has I internal vetices and n vetices. Then we have, n= mi + 1 ……..(1)

                                                                                                                    n = i + l………..(2)

From (1) and (2) l+i = mi + 1

Þ mi – I = l – 1

Þ I (m-1) = l – 1

Þ I =

Again n vertices has I =  internal vertices.

 From (2)  n = I + l

Þ    n =  +1

Þ    n =

Þ    n =

Suppose someone starts chain letter. Each person who receive the letter is asked to send it  on to four other people. Some people do this but others do not send any letter.

How many people have  seen the letter including first person, if no one receive more than one letter and if the chain letters ends after there have been 100 people who read if but did not send it out. How many people send out the letter.

Solution: The chain letter can be represented by 4-ary tree. The internal vertices corresponds the people who send out the letters and the leaves corresponds the people who read it but did not send out. Since 100 people did not send out the letter, the number of leaves of this tree is l = 100.

Hence, the number of people who have seen the letter is (i.e number of  vertices) n =  =  = 133

 Also the internal vertices is I =  =  =  = 33

Hence 33 people send out the letter and 133 people seen the letter.

Definition: The level of a vertex v in  a rooted tree is the length of the unique path from the root of this vertex.

The level of the root is defined to be zero (0). The height of a rooted tree is the maximum of the levels of vertices or the length of the longest path from the root to any vertex.