BINARY TREES

It is a non-linear data structure.

It is a hierarchical data structure. ( OS file

maintenance)

Most general form of a tree can be defined as

an “connected acyclic graph
“.
 TREES

Trees are normally divided into two groups

10 20
General trees :

12 8 20

10

Binary trees : or or
10 10 10

20 12 20
Binary Trees:
A binary is a tree which is a
collection of zero or more nodes. A tree can be
empty or partitioned into three subgroups
namely root , left sub tree and right sub tree.

In general, a tree in which each node

has either zero, one or two sub trees is called a
binary tree.
10 10 10

or or
20 12 20

Root:
Left sub tree:
It is a tree which is connected to the left
of root & it is called left sub tree.

Right sub tree:

It is a tree which is connected to the
right of the root & it is called right sub tree.

In general, a tree in which the out

degree of node has either zero, one or two is
called a binary tree.
Different terminologies normally associated
with trees:

Root node:
A node with in degree O is called root
node it is
the first node in the tree. ( A root is a node
without parent )

Child:
The nodes , which are all reachable from a
node X using only one edge are called children.

Siblings:
Two or more nodes having the same parent
Parent :
A node having left sub tree or right sub
tree or both is said to be a parent node.

Leaf :
A node in a tree that has an out degree of
Zero is called a leaf nodes. ( Leaves are nodes
without children )

Internal nodes :
The nodes except leaf nodes in a tree are
called internal nodes.
Level:
The distance of a node from the root is
called level of the node.

In a tree, the root has a level 0(zero) and

level of any other node is one more than the
level of its father.

Height : (depth) :
The height of the tree is defined as the
maximum level of any leaf in the tree.
Types of binary trees:
The binary trees are classified as follows,

Strictly binary tree

Complete binary tree

Almost Complete binary tree

An expression tree

Binary search tree

AVL trees.
Strictly binary tree :

If the out degree of every node in a tree

is either 0 or 2 , then the tree is said to be
strictly binary tree.

10
Eg : OR 10

12 20
12 20

12
10 12
10
Complete binary tree:
A strictly binary tree in which the
number of nodes at any level i is 2 pow i, is
said to be a complete binary tree.

Eg :
10

12 20

12
10 12 10
Almost Complete binary tree:
It is a strictly binary tree, except the last
level.

Eg :
10

12 20

12
10 12
Storage representation of a binary tree :

The storage representation of binary

trees can be classified as shown below,

Sequential allocation technique (static

allocation )

Linked allocation technique( Dynamic

allocation)
Sequential allocation technique:

A tress can also be represented

using an array which is called sequential
representation.

10
0

12 20
1 2

312 4
10 12 5 10 0
12 201 12 210 12
3 4 5
Linked allocation technique:

In a linked allocation technique a node

in
a tree has three fields,

Info : Which contains actual information

Llink : which contains address of the left sub

tree.

Rlink : which contains address of the right

sub tree.
So, a node can be represented using structure
as shown below,

Struct node
{
int info;
Struct node * llink;
Struct node * rlink;
};

typedef struct node * NODE;

A pointer variable “root” can be used to
point to
the root node always .

If the tree is empty , the pointer

variable root
points to NULL indicating the tree is empty,

i.e., NODE root = NULL;

Various operations on binary trees:

Insertion

Traversal

Search

Display
Insertion :
10

12 20

12
12 12

12 10 temp
10

Now, I want to insert a “ temp “ node for the

above tree .
Insertion :
10

12 20

12
12 12

12 10 temp
10

if you want to insert a “ temp “ node we have

to give the direction as “ RLR “.

 //Algorithm to insert an item into a binary tree based
on direction.

Step 1 : Create a node temp and insert info and

null to left and right fields

Step 2 : If empty tree return temp as first node.

Step3 : Accept the direction to insert and find the

place to insert based on direction string.

Step 4 : If proper place not found, then invalid

direction delete temp node and return back.

Step 5 : Otherwise insert node and return back.

 //function to insert an item into a binary tree based
on direction.
NODE insert(int item, NODE root)
{
NODE temp, cur , prev;
char direction [10];
int i;
temp = getnode();
temp->info = item;
temp-> llink = temp->rlink = NULL;
if (root == NULL) return temp;
Printf(“give the directions where you
want to
insert”);
Scanf(“%s”, direction);
Prev = NULL;
Cur = root;
/* find the position to insert */
for (i=0; i < strlen(direction); i++)
{
if (cur == NULL) break;
prev = cur;
if(direction[i] == ’L’)
cur = cur->llink;
else
cur = cur->rlink;
}
 if (cur != NULL || i! = strlen(direction))
{
printf(“insertion not possible”);
free(temp);
return root;
}
If(direction[i-1]== ’L’ )
Prev->llink = temp;
else
Prev->rlink = temp;
Return root;
}
Traversals :
Traversing is a method of visiting each
node of a tree exactly once in a systematic order.
During traversal, we may print the info
field of each node visited.

Different types of tree traversals:

Preorder
Inorder
Post order
Preorder traversal:

Step 1 : Process the root node

Step 2 : Traverse the left sub tree in preorder
Step 3 : Traverse the right sub tree in preorder

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for preorder traversal.

Void preorder(NODE root)

{
if(root == NULL)
return;
printf(“%d”, root->info);
Preorder(root->llink);
Preorder(root->rlink);
}
// Iterative function for preorder traversal.

Void preorder ( NODE root )

{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{
 while ( cur != NULL )
{
printf ( “ %d “ , cur -> info );
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}
Inorder traversal :

Step 1 : Traverse the left sub tree in Inorder

Step 2 : Process the root node
Step 3 : Traverse the right sub tree in Inorder

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for Inorder traversal

Void inorder(NODE root)

{
if(root == NULL)
return;
Inorder(root->llink);
Printf(“%d”, root->info);
Inorder(root->rlink);
}
// Iterative function for inorder traversal.

Void inorder ( NODE root )

{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{
 while ( cur != NULL )
{
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
printf ( “ %d “ , cur -> info );
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}
Postorder traversal :

Step 1 : Traverse the left sub tree in postorder

Step 2 : Traverse the right sub tree in postorder
Step 3 : Process the root node

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for Inorder traversal

Void postorder(NODE root)

{
if (root == NULL)
return;
postorder(root->llink);
postorder(root->rlink);
printf(“%d”, root->info);
}
// Iterative function for post order traversal.
void postorder( NODE root )
{
struct stack
{
NODE address;
int flag; };
NODE cur;
struct stack s[20];
int top = -1;
if ( root == NULL )
{
printf (“ Tree is empty “);
return;
}
cur = root;
for (; ;)
{
while ( cur != NULL )
{
top++;
s[top].address = cur;
s[top].flag = 1;
cur = cur -> llink;
}
while ( s[top].flag < 0 )
{
cur = s[top].address;
top--;
printf (“%d”, cur -> info );
 if ( top == -1 )
return;
}
cur = s[top].address;
cur = cur -> rlink;
s[top].flag = -1;
}
}
Example : A

B C

D
E F

G H
I

Preorder :-> ABDGHCEIF

Postorder :-> GHDBIEFCA
Inorder :-> GDHBAEICF
// Recursive function to print the tree in tree form.

void display(NODE root, int level)

{
int i;
if (root == NULL) return;
display (root-> rlink; level+1);
for( i=0; i< level; i++)
printf(“ “);
printf(“%d\n”, root->info);
display(root->llink,level+1);
}
//c program to create a tree and traversals
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>

Struct node
{
int info;
Struct node *llink;
Struct node *rlink;
};
typedef struct node * NODE;

/* include all the above functions */

 Void main()
{
NODE root= NULL;
Int choice, item, flag;
For(;;)
{
printf(“1. Insert [Link] [Link]
[Link] 5. Display [Link]”);
printf(“enter the choice”);
Scanf(“%d”, &choice);
Switch(choice)
{
Case 1:
printf(“enter the item to be
inserted”);
 Root=insert( item, root);
Break;
Case 2:
if(root == NULL)
printf(“tree is empty”);
else
{
printf(“ the given tree is”);
printf(root, 1);
printf(“preorder traversal is”);
preorder(root);
printf(“\n”);
}
break;
Case 3 :
if(root==NULL)
printf(“tree is empty);
Else
{
printf(“ the given tree is “):
display(root,1);
printf(“inorder traversal is”);
inorder(root);
printf(“\n”);
}
break;
case 4:
If(root==NULL)
Printf(“tree is empty”);
Else
{
printf(“the given tree is”);
display(root,1);
printf(“postorder traversal is”);
postorder(root);
printf(‘\n”);
}
break;
 Case 5 :
if(root == NULL)
printf(“ tree is empty”);
else
display(root,1);
default :
exit(0);
}
}
}
Examples :
write a binary tree based on the following
traversals,

1. preorder : ABDEGHCFIJ
inorder : DBGEHACIFJ

2. Inorder : GHDEACBFI
Postorder : GDABCEIFH
Binary Search Tree ( BST ) :
A binary search tree is a binary tree in
which for each node in the tree, elements in the left
sub tree are less than root and elements in the
right sub tree are greater than root.
Ex :
100 20

11 10 60
70
0

60 10 40
80 70
5
Insertion:

Ex: 100, 50, 200, 90, 80, 25, 300, 150, 180, 140
// Algorithm to insert an item into a binary search
tree.

Step 1 : Create a node temp and insert info and

null to left and right fields

Step 2 : If empty tree return temp as first node.

Step 3 : Based on info field find out the proper

position to insert temp node.

Step 4 : Insert node and return back.

// function to insert an item into a binary search tree
NODE insert ( int item, NODE root )
{
NODE temp, cur, prev;
temp = getnode ();
temp-> infor = item;
temp-> llink = NULL;
temp-> rlink = NULL;
if(root == NULL) return temp;
prev = NULL;
Cur = root;
while (cur !=NULL)
{
Prev = cur;
 if(item < cur->info)
cur = cur->llink;
else
cur = cur->rlink;
}

if( item < prev->info)

prev->llink = temp;
else
prev->rlink = temp;

return root;
}
Searching:
// c function to search an element in BST
NODE iterative search(int item, NODE root)
{
root1 = root;
if(root1 == NULL) return root;
while(root1 != NULL)
{
if(item == root1->info)
break;
if(item < root1->info)
root1 = root1->llink;
else
root1 = root1->rlink;
}
if(root == NULL)
{
printf(“item not found”);
return root;
}
printf(“key found”);
return root;
}
Disadvantages of Binary trees & BST:
In the above two types the tree can
degenerate into a severely unbalanced one with
height equal to n-1
E.g. : Binary10tree Binary search
100 tree

20
20 30 90
0

40 40

50 70

60 60
AVL Trees:
AVL trees were invented in 1962 by two
Russian scientist G.M Adelson Velsky & E.M Landis.

Definition:
An AVL tree is a binary search tree in
which the balance factor of every node, which is
defined as the difference b/w the heights of the
node’s left & right sub trees is either 0 or +1 or
-1 .
Balance factor = height of left sub tree – height of
right sub
Example :

AVL tree BST ( not AVL tree )

1
2 10 10

0 1 0
5 20 5 20
0

4 4 7
7 12
1 -1 0 1 -
1
2 8
2
8

0 0 0
0
 If an insertion of a new node makes an AVL tree
unbalanced , we transform the tree by a rotation

Rotation :
A Rotation in an AVL tree is a local
transformation of its sub tree rooted at a node whose
balance has become either +2 or -2 ,if there are
several such nodes, we rotate the tree rooted at
the unbalanced node that is the closest to the newly
inserted leaf.
Types of rotations :

Totally there are four types of rotations

1. Single right rotation or R-rotation

2. Single left rotation or L-rotation

3. Double right-left rotation or RL-rotation

4. Double left-right rotation or LR-rotation

Points to remember to select different rotation
technique :

1. Straight line with positive unbalanced.

apply Right rotation for unbalanced node.
5 +2
4
0
4
2 5
+1 0
0
2

0
2. Straight line with negative unbalanced.
apply left rotation for unbalanced node.

-2
5
7 0

-1
7 0
5 9
0
9
0
3. Curved line with positive unbalanced.
apply left-right rotation.

Right rotation for unbalanced node and left

rotation for the nearest node.

+2
5
0
4

3 -1
03 5
0 4
0
4. Curved line with negative unbalanced.
apply right-left rotation.

Left rotation for unbalanced node and right

rotation for the nearest node.

-2
5
0
7

8
+1
5 0 8
07
0
Red-Black Tree
A red-black tree can also be defined as a binary
search tree that satisfies the following properties:
 Root Property: the root is black
 External Property: every leaf is black
 Internal Property: the children of a red node are black
 Depth Property: all the leaves have the same black depth

4 15

2 6 12 21

7
Height of a Red-Black Tree
Theorem: A red-black tree storing n items has
height O(log n)
Proof:
 The height of a red-black tree is at most twice the
height of its associated (2,4) tree, which is O(log n)
The search algorithm for a binary search tree
is the same as that for a binary search tree
By the above theorem, searching in a red-
black tree takes O(log n) time
Insertion
 To perform operation insertItem(k, o), we execute the
insertion algorithm for binary search trees and color red
the newly inserted node z unless it is the root
 We preserve the root, external, and depth properties
 If the parent v of z is black, we also preserve the internal
property and we are done
 Else (v is red ) we have a double red (i.e., a violation of the
internal property), which requires a reorganization of the tree
 Example where the insertion of 4 causes a double red:

6 6
v v
3 8 3 8
z z
4
Remedying a Double Red
 Consider a double red with child z and parent v, and let
w be the sibling of v
Case 1: w is black Case 2: w is red
 The double red is an incorrect  The double red corresponds
replacement of a 4-node to an overflow
 Restructuring: we change the  Recoloring: we perform the
4-node replacement equivalent of a split

4 4
w v w v
2 7 2 7
z z
6 6

4 6 7 2 4 6 7

.. 2 ..
Restructuring
 A restructuring remedies a child-parent double red when the
parent red node has a black sibling
 It is equivalent to restoring the correct replacement of a 4-node
 The internal property is restored and the other properties are
preserved
z
4 6
w v v
2 7 4 7
z w
6 2

4 6 7 4 6 7

.. 2 .. .. 2 ..
Restructuring (cont.)
 There are four restructuring configurations depending on
whether the double red nodes are left or right children

2 6 6 2
6 2 4 4
4 4 2 6

2 6
Recoloring
 A recoloring remedies a child-parent double red when the
parent red node has a red sibling
 The parent v and its sibling w become black and the
grandparent u becomes red, unless it is the root
 It is equivalent to performing a split on a 5-node
 The double red violation may propagate to the grandparent u

4 4
w v w v
2 7 2 7
z z
6 6

… 4 …
2 4 6 7
2 6 7
Analysis of Insertion
Algorithm insertItem(k, o)  Recall that a red-black tree
has O(log n) height
1. We search for key k to locate  Step 1 takes O(log n) time
the insertion node z because we visit O(log n)
nodes
2. We add the new item (k, o) at  Step 2 takes O(1) time
node z and color z red  Step 3 takes O(log n) time
because we perform
3. while doubleRed(z)  O(log n) recolorings, each
if isBlack(sibling(parent(z))) taking O(1) time, and
z  restructure(z)  at most one restructuring
taking O(1) time
return
 Thus, an insertion in a red-
else { sibling(parent(z) is red }
black tree takes O(log n)
z  recolor(z)
time
Red-Black Tree Reorganization
remedy double
Insertion red
Red-black tree action (2,4) tree action result
change of 4-node double red
restructuring
representation removed
double red
recoloring split removed or
propagated up