**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
^{i}⇒2^{l}=2^{i} - 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^{lmax+1}-1/2-1

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

⇒n^{1}+1=(e^{1}+1) +1

⇒n^{1}+1=((n^{1}-1)+1) +1

⇒n^{1}+1=(n^{1}-1+1) +1

⇒n^{1}+1=n^{1}+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_{0} is the number of leaf nodes (degree=0) and n_{2} is the number of internal nodes(degree=2), then n_{0}=n_{2}+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_{0}+n_{1}+n_{2} ........ (i)

If e is the number of edges in T , then

⇒ e=n_{0}×0+n_{1}×1+n_{2}×2

⇒ e=n_{1}+2n_{2} ......... (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_{1}+2n_{2}+1 ...... (iv)

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

⇒n_{0}+n_{1}+n_{2}=n_{1}+2n_{2}+1

⇒n_{0}=1+2n_{2}-n_{2 }n_{0}=n_{2}+1

__Property :6__

____The height of complete binary tree with n number of nodes is log_{2}(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_{2}(n+1)

⇒h=log_{2}(n+1)

__Property :7__

The total number of binary trees possible with n nodes is ^{2n}C_{n} 1/(n+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**:

- Search for the key node in the tree.
- if (l=0) or (The key node is present) then
- printf "No insertion"
- Exist
- end if
- (A[2*l]=NULL) or (A[2*l+1=NULL)
- if (key node had empty links) then
- if (option=l) then
- if (left child is null) then
- insertion as a left child
- else
- printf "Node already has left child:No insertion"
- exit
- end if
- end if
- if(option=R ) then
- if(right child=NULL) then
- insert item as a right child
- else
- printf " node already has right child"
- exit
- end if
- end if
- else
- print "item cannot be inserted as a leaf node"
- end if
- 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__

____i=Index- if (A[i]≠key) then
- if (2*i≤size) then
- search SEQ(2*i, Key)
- else
- if (2*i+1≤size) then
- search SEQ(2*i+1, Key)
- else
- return(0)
- end if
- end if
- else
- return
- end if
- 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__

flag=FALSE

l=search SEQ(l, key)

if l=0 goto step10

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

flag=TRUE

A[l]=NULL

else

print " The node containing ITEM is not a leaf"

end if

if(flag=FALSE)

print "node does not exist"

end if

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: