SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
2k views
in Examples, Exercises and Projects by (562 points)
edited by

Binary tree

  • Its properties.
  • various operations performed in it

1 Answer

0 like 0 dislike
by (562 points)
edited by
 
Best answer

Binary Tree

Properties of Binary Tree

Property 1:

In any binary tree, the maximum number of nodes on level l is 2l where l≥0

Proof:

  • In binary tree , length of the binary tree is l . The root node contains any one node on level 0.
  • Hence , the maximum number of nodes on level 0 is 1→2°=1
  • The maximum number of nodes on level 1 is 2→2¹=2
  • The maximum number of nodes on level 2 is 4→2²=4
  • Same like these. The maximum number of nodes on level l=i is 2i⇒2l=2i 
  • Hence , the maximum number of nodes on level l is 2l.

Fig:

    binary tree

Property 2:

The maximum number of nodes possible in a binary tree of height h is 2h-1.

Proof:

  • The maximum number of nodes in a binary tree is the total count of the maximum number of nodes in at each level. 
  • Then, the maximum number of nodes in a binary tree is height 'h' is:

n=2lmax+1-1/2-1

⇒n=2lmax+1-1

where, lmax is a maximum level of the tree. 

Based on definition of height h, h=lmax+1

Then, n=2h-1

Property:3

The maximum number of nodes possible in a binary tree of height h is h. 

Proof:

  • A binary tree has the minimum number of nodes in each level. 
  • The minimum number of nodes possible at every level is only one node, when ever the parent has one child node. These kind of binary tree is called Skewed Binary Tree. Then , the number of nodes of a binary tree :

nmin=h 

Fig:

        ​​​​​binary tree type

Property 4:

For any non-empty binary tree, if n is the number of nodes and e is the number of edges . 

Then, n=e+1

Proof:

  • For n=1, e=0  then, n=e+1=0+1 ⇒n=1
  • For n=2, e=1 then , n=e+1=1+1⇒n=2
  • For n=3, e=2 then, n=e+1=2+1 ⇒n=3

  • For n=n1, e=n1-1  then, n1=(n1-1)+1
  • Let n1 be the number of nodes, 
  • Thus, n1=e1+1⇒e1=n1-1
  • If we add one more node into the binary tree having n1 nodes, then it will increases one more edge in the binary tree, then

⇒n1+1=(e1+1) +1

⇒n1+1=((n1-1)+1) +1

⇒n1+1=(n1-1+1) +1

⇒n1+1=n1+1

The formula is true when for any number of nodes n, then it is also true for n+1 

Hence, n=e+1 is true. 

Property :5

For any non-empty binary tree T , if n0 is the number of leaf nodes (degree=0) and n2  is the number of internal nodes(degree=2), then n0=n2+1

Proof:

  • Let n be the total number of  nodes in binary tree T . ni be the number of nodes having degree i. 

Since 0≤i≤2 

we have, 

          ⇒   n=n0+n1+n2                    ........ (i) 

If e is the number of edges in T , then 

        ⇒   e=n0×0+n1×1+n2×2

       ⇒    e=n1+2n2                       ......... (ii) 

since , n =e+1                        ................ (iii) 

  • For non-empty binary tree T, if n is  number of nodes and e is number of edges. 

Substitute eq. (ii) in eq(iii) 

⇒n=n1+2n2+1                                ...... (iv) 

Since eq. (i)  and eq. (iv) are equal . Then, 

⇒n0+n1+n2=n1+2n2+1

⇒n0=1+2n2-nn0=n2+1

Property :6

​​​​​​The height of complete binary tree with n number of nodes is log2(n+1) 

Proof:

Let 'h' be the height of the complete binary tree. 

Since, n≤2°+2¹+2²+2³+.......... +2h-1

 ⇒n≤2h-1

⇒n+1≤2h

⇒ 2h≥n+1 

Taking log on both sides, we get

⇒h≥log2(n+1) 

⇒h=log2(n+1) 

Property :7

The total number of binary trees possible with n nodes is  2nCn 1/(n+1) . 

  1. Operations of a Binary Tree

There are  four major representations on a binary tree :

  • Insertion
  • Deletion
  • Traversal
  • Merge

(We will discuss insertion and deletion here) 

Insertion

  • To perform insertion operation, first find out the key element is presented in the tree or not, by using searching operation. Key element is not presented , then perform the insertion operation. 

Algorithm:

  1. Search for the key node in the tree. 
  2. if (l=0) or (The key node is present) then
  3. printf "No insertion"
  4. Exist
  5. end if
  6. (A[2*l]=NULL) or (A[2*l+1=NULL) 
  7. if (key node had empty links) then
  8. if (option=l) then
  9. if (left child is null) then 
  10.  insertion as a left child
  11. else
  12. printf "Node already has left child:No insertion"
  13. exit
  14. end if
  15. end if
  16. if(option=R ) then
  17. if(right child=NULL) then
  18. insert item as a right child
  19. else
  20. printf " node already has right child"
  21. exit
  22. end if
  23. end if
  24. else 
  25. print "item cannot be inserted as a leaf node"
  26. end if
  27. stop

Note:To perform the operations on left child and right child use the structure format. Suppose parent i as a root node , then 2*i as a left child node and 2*i+1 as a right child node.

Example:The given list is 10,11,12,13.The  root node is 10 already inserted into tree. 

                                             binary tree

Step:1

To insert 11 data element as a leaf node in the tree after completion of searching operation . The element not in the binary tree . Then, insert the data item either left child or right child. 

If (2*i==NULL) ⇒(2*i==0) 

Then , binary tree (2*i) =11 

                                binary tree

Fig:11 is inserted as leaf node. 

Step:2 To insert '12' as a link node after completion of step 1 . Inserted as right child of root node. 

    Binary tree(2*i+1) =12

                                             binary tree

Fig:12 is inserted as a right leaf node. 

Step:3 To insert 13 as a link node after completion of step:2 inserted at right child of root node. 

     Binary tree[2*i+1]=13

                                    binary tree

Algorithms for search:

Steps

  1. ​​​​​​i=Index
  2. if (A[i]≠key) then
  3. if (2*i≤size) then
  4. search  SEQ(2*i, Key) 
  5. else
  6. if (2*i+1≤size) then
  7. search SEQ(2*i+1, Key) 
  8. else
  9. return(0) 
  10. end if
  11. end if 
  12. else
  13. return
  14. end if 
  15. stop. 

Deletion:

  • This operation is used to delete any node from any non-empty binary tree. 
  • Here, we will consider the case of deletion of a leaf node in any binary tree. 
  • Deletion operation in various cases of binary trees will be discussed in due time. 

Algorithm

Search

  1. flag=FALSE

  2. l=search SEQ(l, key) 

  3. if l=0  goto step10

  4. if (A[2*l]=NULL) and (A[2*l+1]=NULL) 

  5. flag=TRUE

  6. A[l]=NULL

  7. else

  8. print " The node containing ITEM is not a leaf"

  9. end if

  10. if(flag=FALSE) 

  11. print "node  does not exist"

  12. end if 

  13. stop. 

Example: The binary tree is:

                                          binary tree

Solution:

Step:1 To delete the key element is '11' . Then, first find out the key element is presented or not in the binary queue. 

To perform this operation, use the searching algorithm. 

The key element '11' is located at index i=2 . 

After finding, the key element ,must check if it is leaf node or not. 

If (A[2*i]=NULL)  and (A[2*i+1]=NULL) 

The key element 11 is a leaf node , then  delete it from the binary tree. 

Step:2 

After deletion, binary tree is as follows:

                                                            binary tree


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...