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

0 like 0 dislike
6.4k views

edited

Binary tree

• Its properties.
• various operations performed in it

### For Indian Students- INR 360/- || For International Students- \$9.99/-

S.No.

Course Name

Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence || Labeled as Highest Rated Course by Udemy

Apply Coupon

2.

Complete Machine Learning & Data Science with Python| ML A-Z Apply Coupon

3.

Complete Python Programming from scratch | Python Projects Apply Coupon

0 like 0 dislike
by (562 points)
edited

# 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:

### 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:

​​​​​

### 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)
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: