Graph Theory - Tree - All Job India

Introduction

In this tutorial we will show you what a TREE really is. We will deal with the Binary Tree in details in this tutorial. The images provided will help you to understand the working in a easier manner. If at any moment you do not understand then please post your queries in the comment section and we will respond to them at the earliest.

What is discussed in this tutorial :

Binary Tree and m-way Tree.
How to find the Degree.
Properties of Binary Tree.
Extended Binary Tree
Strictly Binary Tree
Full Binary Tree
Complete Binary Tree

We will begin this tutorial by taking a few examples.


Figure 1.	Figure 2.

We can say that tree is a subset of graph by concluding from above example.

Degree: - No. of child node of a node.

Height: - Highest level of a tree, where root is level 0/1. No. of edges require to go to highest level node where root is level 0.
Binary Tree: - A Binary tree T is defined as a finite set of elements called nodes, such that

T is empty (called null tree/empty tree)
T contains a distinguish node R, called the root of T and the remaining nodes of T form an ordered pair of disjoint binary trees T1 and T2.

This T1 and T2 are called sub trees of T. (Left and Right sub tree)

Properties of Binary Tree: -

Binary tree with n elements/node, where n>0 has exactly n-1 edges.
For any non empty Binary tree, if t0 is the no. of terminal/leaf nodes and t2 is the no. of nodes of degree 2 then t0 =t2 +1
Assuming root belongs at level 0. A binary tree of height h, h≥0, has atleast h+1 nodes and atmost 2n+1-1 . Assuming root belongs at level 1. Atleast h nodes and atmost 2n-1.
Assuming roots belongs at level 0. The height of binary tree that contains n no. of element, n≥0, is atmost n-1 and atleast [log2(n+1)]-1 . Assuming roots belongs at level 1. Atmost n. Atleast [log2(n+1)]-1.
Assume Root=0 (Level)

The maximum no. of nodes on level I of binary tree is 2i, where i≥0.
The maximum no. of nodes on level I of a binary tree is 2i-1 ,whose i≥1.

Extended Binary Tree:

A binary tree T is said to be a 2-tree or extended binary tree if each node M has either ) or 2 children. In such a case the nodes with 2 child are called interval nodes and node with 0 child are called external nodes. E.g.
Total No. of nodes (required to convert a binary tree to extended)= n+1, no. of nodes in non converted binary tree.
To converting binary tree to extended binary tree.

Strictly Binary Tree:

It is kind of binary tree in which every non leaf node has exactly two child. Here, leaf node may be at same level or may not be. E.g.

Full Binary Tree:

It is a kind of binary tree in which all leaf nodes are at same level and all non leaf node has exactly two children. This tree also known as perfect binary tree. E.g.

Complete Binary Tree:

A binary tree is said to be complete if all it’s levels, except possibly the last, have the maximum no. of possible nodes, and if all the nodes at the last level appear as far left as possible. E.g.
height=2
*first left indentation then right.