Page 536 - Computer science 868 Class 12
P. 536

•  3 and 10 are the siblings as they have same parent node 8. Similarly, 1 and 6 are the siblings as their parent node
                 is 3. Similarly, 4 and 7 have same parent 6 and thus are siblings.
              •  The left sub tree of 8 is.

                                                                3




                                                         1            6




                                                                 4         7

              •  The right sub tree of 8 is
                                                                    10




                                                                          15




                                                                    13
              •  6, 4, 7 are descendants of 3.
              •  15, 10, 8 are ancestors of 13.
                                                                                                     8
              13.4.2 Properties of a Tree
              Following are some of the properties of a tree.
                                                                                            3                10
              •  Degree  of a tree:  Maximum  number  of  child  nodes  attached  to  any
                 node of a tree is called its degree. The degree of the given tree is 2 as it
                 has maximum of 2 successor nodes.
                However, degree of any particular node can be different from the degree   1       6                15
                 of the tree. For example,
                Degree of nodes 10 and 15 is 1 while degree of Nodes 8, 3, 6 is 2. Degree
                 of any leaf node is 0. So 1, 4, 7, and 13 have degree 0.                    4         7     13
              •  Level of a tree: The nodes in a tree are assigned a number from root
                 node to leaf node according to its hierarchy. This number is
                 called the level number. The level of root is 0 and it increases           8
                 by 1 as we move down.                                                                           Level 0
              •  Depth of a tree: It is the total number of edges from the         3                10
                 root node to a leaf node in its longest path. The depth of the                                  Level 1
                 given tree is 4 as it has 4 levels from 0 to 3.
                Depth of a node, however, is the total number of edges from   1          6                15
                 the root node to the given node.                                                                Level 2
                Thus, depth of root node 8 is 1.
                Depth of nodes 3 and 10 is 2.                                       4         7     13
                Depth of nodes 1, 6 and 15 is 3.                                                                 Level 3
                Depth of nodes 4, 7, 13 is 4.
                The terms level and depth in a tree are synonymous.



                534534  Touchpad Computer Science-XII
   531   532   533   534   535   536   537   538   539   540   541