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
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
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.
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.
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
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
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,
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
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
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
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}
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.
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 – 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 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
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
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.
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.
Call-by-Value
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
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
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:
Arrays
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.
A queue is also an abstract data structure like the stack, except that the elements are inserted from read and deleted from the front. Therefore, data structures implement such operations are queues. In this document, find all articles related to queue data structures.
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.
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
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
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
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
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
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
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
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
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
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
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
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
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 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.
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.
Find biggest number
Find smallest number
To solve this problem very easily by
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.
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.
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
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
_________________________________________
.
,
.
