Data-structure – Ordered Tree vs Unordered Tree

A binary tree can be ordered or an unordered tree, so what is the difference between these two trees. In this lesson, you will compare the ordered tree vs. unordered tree and tell the difference.

Ordered Tree Example

The name suggests that the ordered tree must be an organized tree in which nodes are in some order. What is the common ordering method?

An Ordered Tree - ordered tree vs. unordered tree
An Ordered Tree

In the figure above, for any node, its left child has less value than the node itself and the right child has a value greater than the node.

Unordered Tree

In a binary tree, when nodes are not in a particular order it is called a unordered tree.

See the root, all the left descendants of the root are less than the root value and all right descendant has a value greater than the root.

Unordered Tree - ordered tree vs. unordered tree
Unordered Tree

This is the primary difference between the ordered tree vs. unordered tree.

References

R.G.Dromey. 2008. How to Solve it by Computer. Pearson Education India.

Robert Kruse, Cl Tondo. n.d. Data Structures and Program Design in C. Pearson Education India.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

Data Structure – Binary Tree Concepts

A binary tree is a special kind of tree and important in computer science. There is plenty of real-world application of binary trees. The scope of this lesson is limited to the learning the binary tree concepts.

Learn Tree Basics

Informal definition

A tree is called a binary tree if it has the following properties.

  • It is an empty tree with no nodes.
  • The tree has a root node, left sub-tree and right sub-tree.
  • The sub-trees are binary tree themselves.

Strictly Binary Tree

Suppose there is a binary tree with right sub-tree and left sub-tree. The sub-trees are in turn non-empty, then such a binary tree is called a strictly binary tree.

Strictly Binary Tree - Binary Tree Concepts
Strictly Binary Tree – Binary Tree Concepts

In the above figure, one is a strictly binary tree and the second tree is not a strictly binary tree, but it is certainly a binary tree and satisfy all the properties of a binary tree.

Complete Binary Tree

A complete binary tree has a level L and all its leaf nodes are available at level L. At each level the complete binary tree contains 2Lnodes.

Let us show this with an example,

Complete Binary Tree - Binary Tree Concepts
Complete Binary Tree – Binary Tree Concepts

The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.

Conversion of a Binary Forest into a Binary Tree

Suppose we have a forest with two trees as follows,

Forest with Two Trees - binary tree concepts
Forest with Two Trees
\begin{aligned}
&T1 = { 1,2,3,4,5,6}\\
&T2 = { 7,8,9,10,11,12}
\end{aligned}

The figure below show the two separate trees  in the forest.

The first step is to order the nodes of both trees using following formula.

  • If a node has left child, then if comes immediately below the node.
  • If a node has another node in the save level, then it becomes the right child of the node.
  • If a node has right child then, ignore it.

Such a representation of two trees is given below.

Forest with Two Ordered Trees - binary tree concepts
Forest with Two Ordered Trees

Your next step should be to join these two tree into one by connecting their roots. This is because the roots of the trees are at the same level. See the figure below

Forest with Two Ordered Trees Joined - Binary tree concepts
Forest with Two Ordered Trees Joined

The new tree is a binary tree, the node at the save level in above diagram becomes the right child. The final tree structure look like the one in figure below.

Final Joined Binary Tree - Binary Tree Concepts
Final Joined Binary Tree

Total Number of Edges

In a complete binary tree, the total number of edges is given by the formula,

\begin{aligned}
2 (N_L - 1)\hspace{1ex} where \hspace{1ex}N_L\hspace{1ex} is \hspace{1ex}total\hspace{1ex} number \hspace{1ex}of\hspace{1ex} leaf \hspace{1ex}nodes.
\end{aligned}

For example, see the tree below.

Complete Binary Tree with Edge Labelled -Binary Tree Concepts
Complete Binary Tree with Edge Labelled

In the above diagram, we have N_L = 8.

Therefore,

\begin{aligned}
&= 2( N_L - 1) \\
&= 2 ( 8 - 1) \\
&= 2 (7) \\
&= 14\hspace{1ex} edges.
\end{aligned}

Height of a Binary Tree

The maximum level of any node of the binary tree is called the height of a binary tree.

For example, see the figure below.

Height Of The Tree - Binary Tree Concepts
Height Of The Tree

In the above tree figure, the maximum level of the tree is 4,

Therefore, the height of the tree is Height(T) = 4.

References

R.G.Dromey. 2008. How to Solve it by Computer. Pearson Education India.

Robert Kruse, Cl Tondo. n.d. Data Structures and Program Design in C. Pearson Education India.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

Data Structure – Tree Basics

A tree is a non-linear data structure. It means you cannot access an element of a tree in a straightforward manner. In this lesson, you learn about tree basics.

This will serve as a foundation for future topics on trees. You can start learning about other topics if familiar with the basics.

Informal definition of Tree

A tree is a set of one or more nodes with a special node called a Root node. Every none points to a left node and a right node. Sometimes left, right or both are missing and a node points to nothing.

Every node is part of some smaller set of nodes called a Sub-tree. Each sub-tree has more sub-trees.

A Tree Node - Tree Basics
A Tree Node

Tree basics – Directed vs Undirected Tree

In an undirected tree, the edge between two nodes has no direction associated with it. However, a directed tree has some important properties.

  • The directed tree is acyclic means there is loop between the nodes.
  • The directed tree is digraph means it is like a graph with direction. Each node has associated edges. If the node pointed by some other node, it is called an In-degree and if the node is pointing to some other node, its called an Out-degree.
  • Root node has in-degree 0 and all other nodes have in-degree of 1.
  • The minimum number of nodes allowed in a directed tree is 1. So, an isolated node is a directed tree.
A Directed Tree - Tree Basics
A Directed Tree with Root, Branch and Leaf Nodes

Leaf Nodes

In a directed tree with nodes that has an out-degree of 0 is called a Leaf node or Terminal node.

In the above figure, 5, 6, 7, 8, 9 are leaf nodes.

Branch Nodes

In a directed tree with all nodes other than root and leaf nodes are called Branch nodes. For example,

In the above figure, 2, 3 and 4 are branch nodes.

Level of a Tree

Suppose you want to reach the node 8 from root node 1, then starting from root node, we go through following path

1 –> 4 –> 8

So, the level of any node is length of its path from the root node. The level of root node is 0 and level of node 8 is 2.

Tree basics – Ordered Tree

Sometimes the directed tree is ordered, that is, at each level the order is specified, and this type of tree is called an Ordered tree.

Tree A and Tree B - Tree Basics
Tree A and Tree B

In the above figure, the Tree A and Tree B are the same tree but ordered differently.

Node degree

The node degree corresponds to number of children of the node. The node 3,4,and 6 in tree A are leaf nodes and has a degree of 0 because it not a parent of any other node.

The node 2 from tree B has a degree of 2 because node 4 and node 3 are its children.

The Concept of Forest

If we delete root node and its edges from tree A or tree B, we will get two separate trees. This particular set of trees is known as a Forest.

For example, we get the following forest after deleting the root. These forest can be represented as sets.They are the same sets.

Forest A ={ (2,3,4),( 5,6)}                                     Forest B = {(5,6),(2,3,4)}

Two Forest - Tree Basics
Two Forest

Descendant and Children of a Node

There is a node called S and it is reachable from node N means there is a path from N to S. Then an such node S is called a Descendant of a node N.

Suppose a node S reachable by a single edge E from node N is called a Child of node N and the node N is a Parent of child node S.

For example, In Tree A

The node 2 and node 5 are children of node 1

The node 3 and node 4 are not children, but descendant of node 1.

Note: We will be using this tree basics terminology in all future lessons. Make yourselves familiar with the concepts.

References

E.Balaguruswamy. 2013. Data Structures Using C. McGraw Hill Education.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

C Function that Implements Call-By-Reference

The main() function in a C program calls other functions. Some functions need arguments and some do not need any arguments. The efficiency of the program sometimes depends on what and how the arguments passed into the function.

This program is written in Dev-C++ version 4 installed on a Windows 7 64-bit system, but you can use any other standard C compiler to compile and run this program.

The program “C function that implements call-by-reference” is intended for beginner and intermediate level learner of C programming. You may need prior knowledge of pointers to understand this program.

Problem Definition

There are two methods of calling a function in the main() function of a C program.

  1. Call-by-Value
  2. Call-by-Reference

In this post, we will only discuss the call-by-reference method. To learn about call-by-value method, read the article below.

C Function that Implements Call-By-Value Method

In call-by-reference method, when the main() function calls another function the actual arguments are not sent, but a reference to the original values of the variable is sent to the function.

The function will use the memory address (the reference) of the original value of the variable and perform operations on it. You must carefully use this method because the original value can be changed during the execution of the program.

For example, we will declare two variable a and b

int a = 3;                          /* Original Values */
int b = 4;                          /* Original Values */

int *p, *q;                        /* Declare two pointers */

p = &a;                             /* Pointer p refers to the memory address of the variable a */
q = &b;                             /* Pointer q refers to the memory address of the variable b */

swap ( p, q );                    /* Pass the memory address of the original value in the function */

Now, in the function swap (), we use the reference to the original value and do the necessary operations.

void swap ( int &a, int &b )
{

         ……………………………..
        ……………………………..
        ……………………………..
}

Flowchart

Flowchart: C Function that Implements Call-By-Reference Method
Flowchart: C Function that Implements Call-By-Reference Method

Program Code

/*PROGRAM TO DEMO CALL-BY-REFERENCE */ 

#include <stdio.h> 
#include <conio.h> 
main() { 
int a,b,i; 
void swap(int *p,int *q); 
int *p, *q; p = &a; q = &b; 

/* Read two Integers */ 

printf("Enter two number A and B:"); 
scanf("%d%d",&a,&b); 

for(i=0;i<35;i++) 
printf("_");printf("\n\n"); 

printf("Before Swap : %d\tB = %d\n",a,b); 

for(i=0;i<35;i++) printf("_");
printf("\n\n"); 

/* Swap the number using function swap() that uses original values of variable A and B */ 

for(i=0;i<35;i++) 
printf("_");printf("\n\n"); 

swap(p,q); for(i=0;i<35;i++) 

printf("_");printf("\n\n"); 

getch(); 
return 0; } 

/* Swap Operations */ 


void swap(int *p, int *q) { 

int temp = 0; temp = *p; 
*p = *q; 
*q = temp; 

printf("After Swap : A = %dtB = %dn",*p,*q); 

}

 

Output

The output of the program is given below.

Output : C Function that Implements Call-By-Reference Method
Output : C Function that Implements Call-By-Reference Method

Stack

Stack is a linear data structure that is widely used in operating systems and many applications. The stack implies an office stack of files in which you put new files on the top and the employee always take care of the newly arrived file first.

Similarly, when a stack is implemented in whichever method you want it to, newly elements are added to or deleted from the top of the stack, and stack operations always take the top elements and work its way downwards until the stack is empty.

Two ways to implement a stack are:

  1. Arrays
  2. Linked Lists

The linked list structures are dynamic but, that doesn’t mean that you can insert or delete element from the middle or somewhere in the list.

Applications of Stack

Here I give you some programs to implement stack to solve a programming problem in different programming languages.

Tower of Hanoi

The Tower of Hanoi game is very useful in understanding the Recurrence relation.

It is a game of moving N disk between 3 needles. However, there are some rules we must follow before moving a disk from one needle to second needle.

Rule 1: Move only one disk at a time and it must be a top one.

Rule 2. Cannot move a larger disk on top of smaller one.

Rule 3: Number of moves should be minimum.

Let see how this works for 3 disk Tower of Hanoi game and using output of the game we can find solution to Tower of Hanoi game for N disk.

Tower of Hanoi - Initial Setup with Pegs
Tower of Hanoi – Initial Setup with Pegs

Initially , our disks stacked in needle 1 and other two remain empty. Each time we move a disk it is counted as 1.

TOH - Disk Move From Needle 1 to Needle 3
TOH – Disk Move From Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

TOH - Move disk from Needle 1 to Needle 2
TOH – Move disk from Needle 1 to Needle 2

Move top disk from needle 1 to needle 2.

TOH - Move disk from Needle 3 to Needle 2
TOH – Move disk from Needle 3 to Needle 2

Move top disk from needle 3 to needle 2.

TOH - Move disk from Needle 1 to Needle 3
TOH – Move disk from Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

TOH - Move disk from Needle 2 to Needle 1
TOH – Move disk from Needle 2 to Needle 1

Move top disk from needle 2 to needle 1.

TOH - Move disk from Needle 2 to Needle 3
TOH – Move disk from Needle 2 to Needle 3

Move top disk from needle 2 to needle 3.

TOH - Move disk from Needle 1 to Needle 3
TOH – Move disk from Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

So we took total 7 Moves to shift all 3 disks.

Let the total number of disk move be H.
If we want to compute total count for 4 disk Tower of Hanoi game.

H_{n}=2(H_{n-1}-1) +1 = 2 . 7 + 1 = 14 + 1 =15

There minimum 15 disk move required for 4 disk Tower of Hanoi game.

We can derive a much easier formula for  H_{n}=2(H_{n-1}-1) +1

= 2^n - 1

How we arrived at this solution, we leave it as an exercise for you.

Linked List

Linked list is a linear data structure that uses dynamic memory to construct the list. There are many types of lists. Since, a list is abstract data type its operations are also different from normal builtin types. In this document, you will find articles related to linked-lists.

Linked List Articles

  • Singly Linked List
  • Inserting And Deleting From Singly Linked List
  • Doubly Linked List
  • Inserting A Node In Doubly Linked List
  • Deleting A Node From Doubly Linked List
  • Circular Linked List
  • Inserting A Node Into Singly Circular Linked List
  • Deleting A Node from Singly Circular Linked List
  • Concatenating Two Singly Circular Linked Lists

Linked List Examples

Data Structure – Queue Basics

Queue is a linear data structure and an abstract data type which is defined using some basic data type in programming languages. A queue data structure is implemented using an array or a linked-list type in a programming language.

There are two pointers that mark both ends of a queue.

  • Front
  • Rear

A queue works on FIFO principle, First In, First out, any element that goes first must come out first.

Figure 1 - Queue Data Structure
Figure 1 – Queue Data Structure

There are 3 operations performed on a queue

  • Enqueue – insert element at the rear of the queue.
  • Dequeue – remove elements from the front of the queue.
  • Display – display elements of queue.

Enqueue Operation

The enqueue operation is performed in rear end of the queue. You cannot insert into queue data structure if queue is full. When the queue has space, the enqueue operation insert an element and update the ‘rear’ pointer by incrementing it.

For example

The current status of a queue is given below.

Figure 2 - Enqueue Operation on Queue
Figure 2 – Enqueue Operation on Queue

Q [1] = 44 and front = 1, Q [3] = 66 and rear = 4

We will insert element 77 at the rear end of the queue, i.e., Q [4] = 77.

new status of the queue after enqueue operation will be following.

Figure 3 - After Enqueue Operation on Queue
Figure 3 – After Enqueue Operation on Queue

Dequeue Operation

Dequeue operation removes an element from the front of the queue. But the queue must not be empty for dequeue operation to work. An element from the front is removed and ‘front’ pointer is updated.

For example

Consider the status of a queue given below

Figure 4 - Dequeue Operation on Queue
Figure 4 – Dequeue Operation on Queue

Q [1] = 34 and front = 1

You decided to delete Q [1], after deletion front = 1 + 1 = 2

The current queue is shown in following diagram,

Figure 5 - After Dequeue Operation on Queue
Figure 5 – After Dequeue Operation on Queue

Display Operation

This is a simple operation where we traverse through the entire queue and display the list of elements. This function is the same for both array and linked-list implementation of a queue data structure.

Types of Queues

There are different types of queues data structure about which we will learn in future lessons. The list of queues is given below.

  • Circular Queue – where there is not end to the queue and elements are added or deleted in circular motion.
  • Priority Queue – elements of queue are in a specific order.
  • Double-Ended Queue – queue elements can be deleted or inserted from both ends.

Queue Empty and Queue full Scenario

Before inserting or deleting from queue we must check for two conditions

  • Is the queue empty?
  • Is the queue full?

Let’s see each scenario in more detail.

Queue Empty Scenario

When queue is initiated both front = rear = 1, but after that when front==rear then it means that the queue is empty and we cannot delete from the queue because that will be an underflow.

For example

Consider an array based empty queue, where front = rear = 1.

Figure 6 - Queue is initialized with front = rear = 1
Figure 6 – Queue is initialized with front = rear = 1

We inserted 55

Q [1] = 55, rear = 1 + 1 = 2, front = 1

This is shown in the following diagram.

Figure 7 - Inserted 55 at the rear
Figure 7 – Inserted 55 at the rear

We inserted another element 66, now the queue is

Q [2] = 66, rear = 2 + 1 = 3, front = 1

Figure 8 - Inserted 66 at the rear
Figure 8 – Inserted 66 at the rear

Now, let’s start deleting all the elements. Delete the first element 55. Then the queue status is as follows.

Rear = 3, front = 1 + 1 = 2 and Q [2] = 66

The element Q [1] = 55 is deleted.

Figure 9 - Deleted 55 at the front of the queue
Figure 9 – Deleted 55 at the front of the queue

Next, we delete the element Q [2] = 66. The status of the queue after deletion is shown below.

Figure 10 - Deleted 66 at the front of the queue
Figure 10 – Deleted 66 at the front of the queue

Now, front = 2 + 1 = 3, rear = 3 and since,

Front == rear

The queue is empty.

Queue Full Scenario

To insert into a queue, you need to check if the queue is full, so when the front == rear + 1, then the queue is full. Any attempt to insert a new element will result in queue overflow.

For example,

Current status of a queue is as follows

Figure 11 - Queue status at the beginning
Figure 11 – Queue status at the beginning

In the diagram above,

Q [1] = 44 and front = 1. Also Q [4] = 77 and rear = 5

Now we want to insert a new element 88 at Q [5].

The new status of the queue will be

Q [1] = 44 and front = 1, Q [5] = 88 and rear + 1 = 5 + 1 = 6

This is shown in the queue data structure diagram below.

Figure 12 - Queue status at the after inserting 88
Figure 12 – Queue status at the after inserting 88

Now finally, you will insert at Q [6] = 99. The status of the queue becomes

Q [1] = 44 and front = 1, Q [6] = 99 and rear + 1 = 6 + 1 = 7.

Figure 12 - Queue status at the after inserting 88
Figure 13 – Queue status at the after inserting 99

The rear value is greater than queue length. Then

rear + 1 = 7 mod 6 = 1

But,

front = rear + 1 = 1

Then the queue is full and we cannot insert more elements.

References

A.A.Puntambekar. 2009. Data Structures And Algorithms. Technical Publications.

E.Balaguruswamy. 2013. Data Structures Using C. McGraw Hill Education.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

C Program to find the biggest and smallest number and its location

Given an array of integer numbers, we sometimes need to find the largest and the smallest number from the array. This is not a problem if the array is already sorted in ascending or descending order.

This program finds the biggest and the smallest number from a given array of integers and also tell the index value (location) of those values.

We have used Dev-C++ 4.9.9.2 compiler installed on a windows 7 64-bit computer to run the program. You can do the same or use any other ANSI standard C compiler to run the program. The program is intended for beginners of C programming language.

Problem Definition

you are given an array of unsorted integers and you want to solve two problems.

  1. Find biggest number
  2. Find smallest number

To solve this problem very easily by

  1. Assigning the first number from the array as the smallest number. You do not know yet, if this is the smallest number, we are just assuming it is.
  2. Compare this smallest assumed value with other elements of the array and if you encounter another smaller value than the current smallest value, the new value becomes the smallest.
  3. Then the process repeats itself, until search procedure is exhausted.

To find the biggest number do the same thing except the first value is assumed to be the largest value in the array.

Flowchart – Find Biggest and Smallest Number

Flowchart - Find Biggest and Smallest Number
Flowchart – Find Biggest and Smallest Number

Program Code

/* program to find the biggest and smallest number in an array of numbers. */

#include <stdio.h>
#include <stdlib.h>

#define SIZE 100 

main() {

/* declare variables array, smallest, biggest,
location_smallest,location_biggest,array_size,i*/

    int array_of_number[SIZE];
    int big_num,small_num,loc_small,loc_big;
    int i,n;

/* Get the size of the array input */

    printf("ENTER THE SIZE OF THE ARRAY:");
    scanf("%d",&n);

/* Get the Array elements */

    printf("GET THE ARRAY ELEMENTS:");

for(i=1;i<=n;i++) {

    scanf("%d",&array_of_number[i]); 

    }

/* Search for the biggest Number and it's location */

    big_num = array_of_number[1];

for(i=1;i<=n;i++) {

    if(big_num <= array_of_number[i]) {

        big_num = array_of_number[i];
        loc_big = i;
    }
}

printf("_________________________________________\n");

printf("The Biggest Number is %d at location = %d\n",big_num,loc_big);

printf("_________________________________________\n");

/* Find smallest number and it's location */

small_num = array_of_number[1];

for(i=1;i<=n;i++) { 

    if(small_num >= array_of_number[i]) {
        small_num = array_of_number[i];
        loc_small = i;
    }
}

printf("___________________________________________\n");

printf("The smallest Number is %d at location = %d\n",small_num,loc_small);

printf("___________________________________________\n");

    getch();
    return 0;
}


Output

ENTER THE SIZE OF THE ARRAY:5
GET THE ARRAY ELEMENTS:53
66
3
6
23
_________________________________________
The Biggest Number is 66 at location = 2
_________________________________________
_________________________________________
The smallest Number is 3 at location = 3
_________________________________________