Some basics about Trees.

Binary Tree:

A binary tree is a finite set of elements that is either empty or divided into three disjoint sets namely

1.A set containing a single element called root node.
2.A left subtree( can be empty)
3.A right subtree.(can be empty)

So from the above definition , a tree is defined in terms of itself only , recursively.

In a nut shell we can say in a binary tree ea can have atmost two child for each node.Further more the term disjoint plays an important role in the definition of the binary tree. You infer why .

Note that there is no restrictions on the values of the right and left sub-tree in a tree. ( like all those values in left subtree must be less than or equal to root nodes value etc.. )

There are concepts like ancestor,descendant, father, brother etc.. which I am not going to discuss as ;they are analogous to the usual blood relationships and user an easily understand those concepts. Can take it as an excercise.

Before diving into the properties of Binary trees lets see some more definitions .

Level of a node in a binary tree is defined as follows:
1. Level of root node is 0.
2.Level of node n is level of node n's father +1.

Depth of a binary tree is the maximum level of any leaf node in the tree.


Now lets discuss some of the properties of the Binary trees:

Property : The maximum number of nodes at level  'i' in a binary tree is 2ⁱ

Proof:

Induction basis:

We know that the no of nodes at level 0 is 1. i.e root node.

So when n=0  2ⁿ =1

So true for n=0

Induction Hypothesis:

Lets consider that  no of nodes at level K is 2^k for some n=k.

Now we have to show that 2^k+1 is true for n=k+1.

From the inductin hypothesis we have 2^k node at level K. From the definition of binary tree each node can have atmost two children. Therefore at K+1 level , considering each node at level K can have amost two children,

no of nodes at level K+1 <=2^K *2
                                       <=2^K+1

Hence proved.



Property:

The maximum no of nodes in a binary tree of depth K is 2^K+1-1.

Proof:

from the above proof maximum no of nodes at level k is 2^k , at K-1 is 2^k-1 ....

total no of nodes is <=2^k+2^k-1+... +2⁰
                              <=2^k+1-1 ( By induction we can prove this )


 Property:

For any non-empty binary tree T, if n0 is the no. of leaf nodes & n2 is the no. of nodes of degree 2, then n0 = n2 + 1.

Proof:Let n be the total no. of nodes in binary tree.

            n0 no. of nodes of degree 0

            n1  no. of nodes of degree 1

            n2  no. of nodes of degree 2

                        n = n0 + n1 + n2  -----> (1)

            All the nodes except the root node has a branch coming into it. Let B be the no. of branches in the binary tree.

                        n = B + 1 ----->(2)

                        B = 0.n0 + 1 * n1 + 2*n2 since there would be 0 branches from n0, and 1 branch from n1 nodes and two branches from n2 nodes

                        B = n1 + 2n2    ---->3

            Substituting (3) in (2).

                        n =  n1 + 2n2 + 1  ----> 4.

            Equate 1 & 4

                        n0 + n1 + n2 = n1 + 2n2 + 1

                        n0 = n2 + 1

Proved.

Strictly Binary Tree:
If every non leaf node in a binary tree has non empty left and right sub trees, then the tree is termed as strictly binary tree.

So , from the definintion , it is evident that strictly binary tree contains nodes of degree 2 or 0 but not 1.

Property:

The strictly binary tree with n leaf nodes contains 2n-1 nodes.

Proof:

Let number of nodes in Strictly binary tree be N.

Then N=n0+n1+n2. where n0,n1 and n2 are no of nodes of degree 0,1 ad 2 respectively.

From the definition of Strictly binary tree n1=0. as there wont be any nodes of degree 1.

==> N=n0+n2.

From the property of binary trees n0=n2+1.

==> N=n0+n0-1

==> N=2n0-1

if we consider no of leaf nodes =n this implies n=n0.

therefore N=2n-1.

Hence proved.

Complete Binary tree or full Binary tree:

A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. That is in Complete binary tree only nodes of degree 2 or 0 exist . further more all leaves would be at the same level .

As we have seen , in a binary tree with depth d, the maximum possible no of nodes is pow(2,d+1)-1 ( proved above) the maximum case occurs when the binary tree is a complete binary tree.

So when given the depth of full binary tree we compute the no of nodes as pow(2,d+1)-1.

Given the no of nodes we can compute the depth as log(n+1) -1 in base 2.