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