Question

1. Suppose the address of vertex v in the ordered rooted tree T is 4.5.4.6. At what level is v? What is the address of the parent of v? What is the least number of siblings v can have? What is the smallest possible number of vertices in T? If v has two children, what are their addresses? 2. Suppose the address of vertex v in the ordered rooted tree T is 4.3.5.3.4. At what level is v? What is the address of the parent of v? What is the least number of siblings v can have? What is the smallest possible number of vertices in T? If v has two children, what are their addresses?

Answer 1

SOL:

Given the address of the vertex V in the ordered root tree is 4.5.4.6

1) Level of V:

Each value in the address of the vertex V represents the level of the tree . Each value is seperated by dots. First value represents the first level , second value represents the second level, Third value represents the third level,fourth value represents fourth level.

Since the address contains four values the last value represents the 4th level and this is the level at which vertex V is present on . So vertex V is at level 4

2) Address of parent of V:

The children of vertex labelled with V are V.1,V.2,V.3,.... from left to right

If vertex V has address V.k then its parent address is V

Thus if vertex V has address 4.5.4.6 then it's parent address is 4.5.4

so address of parent of V is 4.5.4

3) Least number of sibblings of V have:

The vertex V has address 4.5.4.6 that means last value 6 in the address means parent of vertex V having 6 children

in that 6 children V is one of them that means V has atleast 5 sibblings

so vertex V has atleast 5 sibblings

4) Smallest possible number of vertices in V:

The address of vertex V is 4.5.4.6

The tree should have root node present at first level. so level 1 contains 1 node

The value 4 represents 4 vertices at level 2 and these vertices needs to children of the Level 1

The value 5 represents 5 vertices at level 3 and these vertices needs to children of the Level 2

The value 4 represents 4 vertices at level 3 and these vertices needs to children of the Level 3

The value 6 represents 6 vertices at level 4 and these vertices needs to children of the Level 4

The smallest possible number of vertices in tree are 1+4+5+4+6 = 20

5) The two children address of V :

The vertex V is at level 4 the children of V are present at level 5

so the addresses children of vertex V are

4.5.4.6.1 ---> first children address

4.5.4.6.2 ----> second children address

2) Given the address of vertex V in the ordered root tree is 4.3.5.3.4

1) Level of V:

Each value in the address of the vertex V represents the level of the tree . Each value is seperated by dots. First value represents the first level , second value represents the second level, Third value represents the third level,fourth value represents fourth level and fifth value represents 5th level

Since the address contains four values the last value represents the 5th level and this is the level at which vertex V is present on . So vertex V is at level 5

2) Address of parent of V:

The children of vertex labelled with V are V.1,V.2,V.3,.... from left to right

If vertex V has address V.k then its parent address is V

Thus if vertex V has address 4.3.5.3.4 then it's parent address is 4.3.5.3

so address of parent of V is 4.3.5.3

3) Least number of sibblings of V have:

The vertex V has address 4.3.5.3.4 that means last value 4 in the address means parent of vertex V having 4 children

in that 4 children V is one of them that means V has atleast 3 sibblings

4) Smallest possible number of vertices in V:

The address of vertex V is 4.3.5.3.4

The tree should have root node present at first level. so level 1 contains 1 node

The value 4 represents 4 vertices at level 2 and these vertices needs to children of the Level 1

The value 3 represents 3 vertices at level 3 and these vertices needs to children of the Level 2

The value 5 represents 5 vertices at level 4 and these vertices needs to children of the Level 2

The value 3 represents 3 vertices at level 5 and these vertices needs to children of the Level 5

The value 4 represents 4 vertices at level 6 and these vertices needs to children of the Level 5

The smallest possible number of vertices in tree are 1+4+3+5+3+4 =20

5) The two children address of V :

The vertex V is at level 5 the children of V are present at level 6

so the addresses children of vertex V are

4.3.5.3.4.1 ---> first children address

4.3.5.3.4.2 ----> second children address