Tree, Graph, Binary Tree and BST Operations

Tree:

A tree data structure, like a graph, is a collection of nodes.
There is a root node.
The node can then have children nodes.
The children nodes can have their own children nodes called grandchildren nodes.
This repeats until all data is represented in the tree data structure.
The image below shows a tree data structure.
A tree is a graph that has no cycles.
A child node can only have one parent.
For this reason trees are not a recursive data structure.

Graphs:

Graphs evolved from the field of mathematics.
They are primarily used to describe a model that shows the route from one location to another location.
Def:

A graph consists of a set of nodes and a set of edges.
An edge is a pair of nodes that are connected.

A path is the term used to describe traveling between nodes that share an edge.
The image below shows a graph with 3 nods and 3 edges.

Applications of Tree and Graph:

Finding a path between two nodes, finding the shortest path from one node to another and finding the shortest path that visits all nodes.
The traveling salesman problem is a great example of using a tree algorithm to solve a problem.

Graph Vs Tree:
1

Graph is a non-linear data structure.
Tree is a non-linear data structure.

It is a collection of vertices/nodes and edges.
It is a collection of nodes and edges.

Each node can have any number of edges.
General trees consist of the nodes having any number of child nodes.
But in case of binary trees every node can have at the most two child nodes.

There is no unique node called root in graph.
There is a unique node called root in trees.

A cycle can be formed.
There will not be any cycle.

Applications: For finding shortest path in networking graph is used.
Applications: For game trees, decision trees, the tree is used.

Binary Tree:

Tree represents the nodes connected by edges.
A binary tree has a special condition that each node can have a maximum of two children.
A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Important Terms

Path − Path refers to the sequence of nodes along the edges of a tree.
Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
Parent − Any node except the root node has one edge upward to a node called parent.
Child − The node below a given node connected by its edge downward is called its child node.
Leaf − The node which does not have any child node is called the leaf node.
Subtree − Subtree represents the descendants of a node.
Visiting − Visiting refers to checking the value of a node when control is on the node.
Traversing − Traversing means passing through nodes in a specific order.
Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Search Tree Representation:

A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

Tree Node

The code to write a tree node would be similar to what is given below. It has a data part and references to its left and right child nodes.

struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};

In a tree, all nodes share a common construct.

BST Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following −

Insert − Inserts an element in a tree/create a tree.
Search − Searches an element in a tree.
Preorder Traversal − Traverses a tree in a pre-order manner.
Inorder Traversal − Traverses a tree in an in-order manner.
Postorder Traversal − Traverses a tree in a post-order manner.

Insert Operation

The very first insertion creates the tree.
Afterwards, whenever an element is to be inserted, first locate its proper location.
Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data.
Otherwise, search for the empty location in the right subtree and insert the data.
Algorithm

If root is NULL
then create root node
return

If root exists then
compare the data with node.data

while until insertion position is located

If data is greater than node.data
goto right subtree
else
goto left subtree

endwhile

insert data

end If

Search Operation

Whenever an element is to be searched, start searching from the root node, then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree.
Follow the same algorithm for each node.
Algorithm

If root.data is equal to search.data
return root
else
while data not found

If data is greater than node.data
goto right subtree
else
goto left subtree

If data found
return node
endwhile

return data not found

end if

Traversal Algorithms:

Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root (head) node.
That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree −

In-order Traversal
Pre-order Traversal
Post-order Traversal

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.
In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree.
We should always remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.
We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be D → B → E → A → F → C → G

Algorithm

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be A → B → D → E → C → F → G

Algorithm

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.
We start from A, and following Post-order traversal, we first visit the left subtree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be D → E → B → F → G → C → A
Algorithm

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Example:

#include

struct node {

int data;

struct node* left;

struct node* right;

};

struct node* createNode(value){

struct node* newNode = malloc(sizeof(struct node));

newNode->data = value;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

struct node* insertLeft(struct node *root, int value) {

root->left = createNode(value);

return root->left;

}

struct node* insertRight(struct node *root, int value){

root->right = createNode(value);

return root->right;

}

void main(){

struct node *root = createNode(1);

insertLeft(root, 2);

insertRight(root, 3);

printf("%d %d %d", root->data, root->left->data, root->right->data);

}

Example:

#include

struct node {

int data;

struct node* left;

struct node* right;

};

void inorder(struct node* root){

if(root == NULL) return;

inorder(root->left);

printf("%d ->", root->data);

inorder(root->right);

}

void preorder(struct node* root){

if(root == NULL) return;

printf("%d ->", root->data);

preorder(root->left);

preorder(root->right);

}

void postorder(struct node* root) {

if(root == NULL) return;

postorder(root->left);

postorder(root->right);

printf("%d ->", root->data);

}

struct node* createNode(value){

struct node* newNode = malloc(sizeof(struct node));

newNode->data = value;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

struct node* insertLeft(struct node *root, int value) {

root->left = createNode(value);

return root->left;

}

struct node* insertRight(struct node *root, int value){

root->right = createNode(value);

return root->right;

}

int main(){

struct node* root = createNode(1);

insertLeft(root, 12);

insertRight(root, 9);

insertLeft(root->left, 5);

insertRight(root->left, 6);

printf("Inorder traversal \n");

inorder(root);

printf("\nPreorder traversal \n");

preorder(root);

printf("\nPostorder traversal \n");

postorder(root);

}

Tree, Graph, Binary Tree and BST Operations

Contact Form