treeBasics

-> Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically.

-> Binary Tree is a special datastructure used for data storage purposes.
  Binary as the name suggests means "two".
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
Following are the important terms with respect to tree.
  1.)Path − Path refers to the sequence of nodes along the edges of a tree.
  2.)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.
  3.)Parent − Any node except the root node has one edge upward to a node called parent.
  4.)Child − The node below a given node connected by its edge downward is called its child node.
  5.)Leaf − The node which does not have any child node is called the leaf node.
  6.)Subtree − Subtree represents the descendants of a node.
  7.)Visiting − Visiting refers to checking the value of a node when control is on the node.
  8.)Traversing − Traversing means passing through nodes in a specific order.
  9.)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.
  10.)keys − Key represents a value of a node based on which a search operation is to be carried out for a node.
  
 ->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 common construct.

-> BST Basic Operations
The basic operations that can be performed on a binary search tree data structure, are the following −
 1.) Insert − Inserts an element in a tree/create a tree.
 2.) Search − Searches an element in a tree.
 3.) Preorder Traversal − Traverses a tree in a pre-order manner.
 4.) Inorder Traversal − Traverses a tree in an in-order manner.
 5.) Postorder Traversal − Traverses a tree in a post-order manner.

We shall learn creating (inserting into) a tree structure and searching a data item in a tree in this topic.

->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      

# Implementation

The implementation of insert function should look like this −

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

-> 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      

# Implementation

The implementation of this algorithm should look like this.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

->Traversal:

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 −
1.)  In-order Traversal
2.)  Pre-order Traversal
3.)  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.

1.)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.

# Algorithm

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

2.)Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

# Algorithm

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

3.)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.

# Algorithm

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