What are the properties of binary tree and describe its various operations in it?

Question

Binary tree

• Its properties.
• various operations performed in it

Answer 1

Binary Tree

Properties of Binary Tree

Property 1:

In any binary tree, the maximum number of nodes on level l is 2^l 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 2ⁱ⇒2^l=2ⁱ 
• Hence , the maximum number of nodes on level l is 2^l.

Fig:

    

Property 2:

The maximum number of nodes possible in a binary tree of height h is 2^h-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=2^l_max+1-1/2-1

⇒n=2^l_max+1-1

where, l_max is a maximum level of the tree. 

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

Then, n=2^h-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 :

n_min=h 

Fig:

        ​​​​​

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=n¹, e=n¹-1  then, n¹=(n¹-1)+1
• Let n¹ be the number of nodes, 
• Thus, n¹=e¹+1⇒e¹=n¹-1
• If we add one more node into the binary tree having n¹ nodes, then it will increases one more edge in the binary tree, then

⇒n¹+1=(e¹+1) +1

⇒n¹+1=((n¹-1)+1) +1

⇒n¹+1=(n¹-1+1) +1

⇒n¹+1=n¹+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 n₀ is the number of leaf nodes (degree=0) and n₂  is the number of internal nodes(degree=2), then n₀=n₂+1

Proof:

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

Since 0≤i≤2 

we have, 

          ⇒   n=n₀+n₁+n₂                    ........ (i) 

If e is the number of edges in T , then 

        ⇒   e=n₀×0+n₁×1+n₂×2

       ⇒    e=n₁+2n₂                       ......... (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=n₁+2n₂+1                                ...... (iv) 

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

⇒n₀+n₁+n₂=n₁+2n₂+1

⇒n₀=1+2n₂-n₂ n₀=n₂+1

Property :6

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

Proof:

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

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

 ⇒n≤2^h-1

⇒n+1≤2^h

⇒ 2^h≥n+1 

Taking log on both sides, we get

⇒h≥log₂(n+1) 

⇒h=log₂(n+1) 

Property :7

The total number of binary trees possible with n nodes is  ²ⁿC_n 1/(n+1) . 

2. 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. 

                                             

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 

                                

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

                                             

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

                                    

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:

                                          

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:

                                                            

---