Page 538 - Computer science 868 Class 12
P. 538

Example 2:
                                            9
                                                                                          Height of the left sub tree is 2
                                                                                          Height of the right sub tree is 5
                                      5           12
                                                                                          Difference in height is 3.
                                                                                          So, this tree is un balanced.

                                                       23




                                                            29



                                                                  47



              Complete binary tree: A complete binary tree is a special binary tree where all the levels are completely filled except
              the last level which is filled from the left. Thus, all the leaf elements must lean to the left.

                                                                     1



                                                               2           3



                                                         6


              13.4.4 Binary Tree traversal
              Tree traversing means visiting each node of the tree in a definite manner. Three are three types of tree traversal as
              given below.
              •  Pre Order traversal (Root, Left, Right)
                Algorithm is as follows:
                    Visit the root
                    Traverse the left node
                    Traverse the right node
              •  Post Order traversal (Left, Right, Root)
                Algorithm is as follows:
                    Traverse the left node
                    Traverse the right node
                    Visit the root
              •  In Order traversal (Left, Root, Right)
                Algorithm is as follows:
                    Traverse the left node
                    Visit the root
                    Traverse the right node

              Thus, the order of traversal is denoted by the traversal of root. In pre order it is visited at first, in post order it is visited
              at last and in order it is visited second.



                536536  Touchpad Computer Science-XII
   533   534   535   536   537   538   539   540   541   542   543