BINARY TREE AND ITS PROPERTIES PROOF


BINARY TREE

An important category of general tree is Binary Tree. A  binary tree can be defined as a finite collection of nodes where each node is having the property that it can have 0,1 or 2 children.

A binary tree may be empty known as Null tree or it contains a special node called the root of the tree and remaining nodes in the tree form the left and right binary sub-trees.

                                                   fig. (a) A binary tree

Here, the node A is the root of the binary tree which is the top of the tree.

B and C are the left and right sub-trees of the root A, respectively.

The left sub-tree namely B, having single node D.

The right sub-tree namely C having two nodes E and F.

Similar Binary tree

Two trees are called similar if both are having same structure but the elements in both the tree can be different as shown in fig. b

                                                 fig. b similar binary tree




Equivalent Binary tree

Two trees are called equivalent if both are having same structure and having the same content in their respective nodes.

Complete binary Tree 

A binary tree is called complete if it contains the maximum number of nodes it can have as shown in fig. c

                                            fig. c   complete binary tree

On the other hand, a binary tree is said to be almost complete binary tree if all its levels are full except the last one as shown in fig. d

 

fig. d almost complete binary tree


In fig. c , at level k, there can be maximum 2^k nodes. therefore,

 level 0 can have 2^0=1 node.

 level 1 can have 2^1=2 nodes. 

 level 2 can have 2^2=4 nodes and so on.

Strictly Binary tree

A binary is called Strictly binary tree if all the non leaf nodes of the tree contains exactly two children.

It means , every non-leaf nodes contains left and right sub-tree.

It is also known as 2- tree or full Binary tree or extended binary tree.

It contains exactly 2n-1 nodes.

                                                  fig.e  strictly binary tree

 

CHECK PROPERTIES OF BINARY TREE WITH PROOF