Loading....
Coupon Accepted Successfully!

 

Question 11

Find the closest ancestor of two nodes in a tree.
 


Here is some working C code...


#include 

typedef struct node
{
  int value;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
mynode *closestAncestor(mynode* root, mynode* p, mynode* q);


int main(int argc, char* argv[])

  mynode *node_pointers[7], *temp;
  root = NULL;
  
  // Create the BST. 
  // Store the node pointers to use later...
  node_pointers[0] = add_node(5);
  node_pointers[1] = add_node(1);
  node_pointers[2] = add_node(-20);
  node_pointers[3] = add_node(100);
  node_pointers[4] = add_node(23);
  node_pointers[5] = add_node(67);
  node_pointers[6] = add_node(13);
  
    
  printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
  levelOrderTraversal(root);


  // Calculate the closest ancestors of a few nodes..

  temp = closestAncestor(root, node_pointers[5], node_pointers[6]);
  printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
         node_pointers[5]->value,
         node_pointers[6]->value,
         temp->value);


  temp = closestAncestor(root, node_pointers[2], node_pointers[6]);
  printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
         node_pointers[2]->value,
         node_pointers[6]->value,
         temp->value);
         
         
  temp = closestAncestor(root, node_pointers[4], node_pointers[5]);
  printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
         node_pointers[4]->value,
         node_pointers[5]->value,
         temp->value);
         
         
  temp = closestAncestor(root, node_pointers[1], node_pointers[3]);
  printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
         node_pointers[1]->value,
         node_pointers[3]->value,
         temp->value);         


  temp = closestAncestor(root, node_pointers[2], node_pointers[6]);
  printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
         node_pointers[2]->value,
         node_pointers[6]->value,
         temp->value);  
 
}


// Function to add a new node to the tree..
mynode *add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
     
   return(temp);  
     
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0};
  int size = 0;
  int queue_pointer = 0;
  
  while(root)
  {
      printf("[%d] ", root->value);

      if(root->left)
      {
        queue[size++] = root->left;
      }

      if(root->right)
      {
        queue[size++] = root->right;
      }
      
      root = queue[queue_pointer++];    
  }
}


// Function to find the closest ancestor...
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
   mynode *l, *r, *tmp;

   if(root == NULL)
   {
      return(NULL);
   }
   
   if(root->left==p || root->right==p || root->left==q || root->right==q)
   {
     return(root);
   }
   else
   {
      l = closestAncestor(root->left, p, q);
      r = closestAncestor(root->right, p, q);
      
      if(l!=NULL && r!=NULL)
      {
        return(root);
      }  
      else
      {
         tmp = (l!=NULL) ? l : r;
         return(tmp);
      }
   }
}





Here is the tree for you to visualize...


                        5 (node=0)
        
       1 (node=1)                   100 (node=3)

-20 (node=2)                 23 (node=4)
                   
                   13 (node=5)   67 (node=6)  







Here is the output...


LEVEL ORDER TRAVERSAL

[5] [1] [100] [-20] [23] [13] [67]


Closest ancestor of [67] and [13] is [23]

Closest ancestor of [-20] and [13] is [5]

Closest ancestor of [23] and [67] is [100]

Closest ancestor of [1] and [100] is [5]

Closest ancestor of [-20] and [13] is [5]







**



Question 12

Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.
 


The code below prints the paranthesized form of a tree.


infix_exp(p)
{
   if(p)
   {
      printf("(");
      infix_exp(p->left);
      printf(p->data);
      infix_exp(p->right);
      printf(")");
   }
}




Creating a binary tree for a postfix expression


mynode *create_tree(char postfix[])
{
   mynode *temp, *st[100];
   int i,k;
   char symbol;

   for(i=k=0; (symbol = postfix[i])!='\0'; i++)
   {
        temp = (mynode *) malloc(sizeof(struct node));
        temp->value = symbol;
        temp->left = temp->right = NULL;

        if(isalnum(symbol))
              st[k++] = temp;
        else
        {
              temp->right = st[--k];
              temp->left  = st[--k];
              st[k++]     = temp;
        }
   }
   return(st[--k]);
}




Evaluate a tree


float eval(mynode *root)
{
   float num;

   switch(root->value)
   {
        case '+' : return(eval(root->left) + eval(root->right)); break;
        case '-' : return(eval(root->left) - eval(root->right)); break;
        case '/' : return(eval(root->left) / eval(root->right)); break;
        case '*' : return(eval(root->left) * eval(root->right)); break;
        case '$' : return(eval(root->left) $ eval(root->right)); break;
        default  : if(isalpha(root->value))
                   {
                      printf("%c = ", root->value);
                      scanf("%f", &num);
                      return(num);
                   }
                   else
                   {
                      return(root->value - '0');
                   }

   }
}



Question 13

Write a C program to delete a tree (i.e, free up its nodes)
 


Free up the nodes using Postorder traversal!.

Question 14

How do you convert a tree into an array?
 


The conversion is based on these rules


If i > 1, i/2 is the parent
If 2*i > n, then there is no left child, else 2*i is the left child.
If (2*i + 1) > n, then there is no right child, else (2*i + 1) is the right child. 



Converting a tree to an array is very easy

Suppose we have a tree like this


      A
  B       C
 D E     F G


The array representation would be


a[1] a[2] a[3] a[4] a[5] a[6] a[7]
  A    B    C    D    E    F    G



That is, for every node at position i in the array, its left child will be stored at position (2*i) and right child at (2*i + 1). The root starts at position 1.

Question 15

What is an AVL tree?
 


AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion and lookup times. AVL trees overcome this problem.

An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.


Balance factor of each node = height of right subtree at that node - height of left subtree at that node.



Please be aware that we are talking about the height of the subtrees and not the weigths of the subtrees. This is a very important point. We are talking about the height!.


Here is some recursive, working! C code that sets the Balance factor for all nodes starting from the root....


#include 

typedef struct node
{
  int value;
  int visited;
  int bf;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
int setbf(mynode *p);


// The main function
int main(int argc, char* argv[])

  root = NULL;
  
  // Construct the tree..
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  
  // Set the balance factors
  setbf(root);
  
  printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
  levelOrderTraversal(root);
  getch();
}

// Function to add a new node to the tree...
mynode *add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->visited = 0;
   temp->bf = 0;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     //printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
     
   return(temp);  
     
}


// Recursive function to set the balancing factor
// of each node starting from the root!
int setbf(mynode *p)
{
   int templ, tempr;
   int count;
   count = 1;

   if(p == NULL)
   {
     return(0);
   }
   else
   {
       templ = setbf(p->left);
       tempr = setbf(p->right);

       if(templ           count = count + tempr;
       else
         count = count + templ;
   }

   // Set the nodes balancing factor.
   printf("\nNode = [%3d], Left sub-tree height = [%1d], Right sub-tree height = [%1d], BF = [%1d]\n", 
          p->value, templ, tempr, (tempr - templ));
   p->bf = tempr - templ;
   return(count);
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0};
  int size = 0;
  int queue_pointer = 0;
  
  while(root)
  {
      printf("\n[%3d] (BF : %3d) ", root->value, root->bf);

      if(root->left)
      {
        queue[size++] = root->left;
      }

      if(root->right)
      {
        queue[size++] = root->right;
      }
      
      root = queue[queue_pointer++];    
  }
}



And here is the output...


Node = [-20], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [  1], Left sub-tree height = [1], Right sub-tree height = [0], BF = [-1]
Node = [ 13], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 67], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 23], Left sub-tree height = [1], Right sub-tree height = [1], BF = [0]
Node = [100], Left sub-tree height = [2], Right sub-tree height = [0], BF = [-2]
Node = [  5], Left sub-tree height = [2], Right sub-tree height = [3], BF = [1]


LEVEL ORDER TRAVERSAL

[  5] (BF :   1)
[  1] (BF :  -1)
[100] (BF :  -2)
[-20] (BF :   0)
[ 23] (BF :   0)
[ 13] (BF :   0)
[ 67] (BF :   0)





Here is the tree which we were dealing with above


            5
       1         100
-20           23
           13   67





After insertion, the tree might have to be readjusted as needed in order to maintain it as an AVL tree. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees, possibly stored at nodes. If, due to an instertion or deletion, the tree becomes unbalanced, a corresponding left rotation or a right rotation is performed on that tree at a particular node. A balance factor > 1 requires a left rotation (i.e. the right subtree is heavier than the left subtree) and a balance factor

Here is some pseudo code to demonstrate the two types of rotations...


Left rotation


BEFORE 

        0 (par)
    
   0          0 (p)

         0         0 (tmp)

       0   0     0   0 
                (a) (b)




Here we left rotate the tree around node p



tmp         = p->right;
p->right    = tmp->left;
tmp->left   = p;

if(par)
{
   if(p is the left child of par)
   {
     par->left=tmp;
   }
   else 
   {
     par->right=tmp;
   }
}
else
{
   root=tmp;
}

// Reclaculate the balance factors
setbf(root);





AFTER
        0 (par)
    
   0             0
               (tmp)

          0           0
         (p)         (b)

      0      0    
            (a)

   0     0     
              






Right rotation


BEFORE

        0 (par)
    
   0            0 (p)

         0 (tmp)      0 

      0    0       0     0
     (a)  (b)




Here we right rotate the tree around node p


tmp         = p->left;
p->left     = tmp->right;
tmp->right  = p;

if(par)
{
   if(p is the left child of par)
   {
     par->left=tmp;
   }
   else 
   {
     par->right=tmp;
   }
}
else
{
   root=tmp;
}

// Recalculate the balancing factors...
setbf(root);





AFTER

        0 (par)
    
   0            0 (tmp)

          0           0
         (a)         (p)

                 0         0
                (b)          

                        0     0





**



Question 16

How many different trees can be constructed using n nodes?
 


Good question!

Its


2^n - n


So, if there are 10 nodes, you will have (1024 - 10) = 1014 different trees!! Confirm it yourself with a small number if you dont believe the formula.

Question 17

A full N-ary tree has M non-leaf nodes, how many leaf nodes does it have?
 


Use Geometric progression.


M + (N ^ (n-1)) = (1 - (N ^ n)) / (1 - N)

Here (N ^ (n-1)) is the number of leaf-nodes.

Solving for this leads to the answer

Leaf nodes = M * (N - 1) + 1




Suppose you have a 3-ary tree


                A
      B         C         D
   E  F  G   H  I  J   K  L  M




So, here M=4 and N=3. So using the formula above,


Leaf nodes = M * (N - 1) + 1 = 4 * (3 - 1) + 1 = 9 


Question 18

Implement Breadth First Search (BFS) and Depth First Search (DFS)
 


Depth first search (DFS)

Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors, which means that we're done. The recursion (stack) guides us through the graph.





public void depthFirstSearch(Vertex v)
{
        v.visited = true;

        // print the node

        for(each vertex w adjacent to v)
        {
           if(!w.visited)
           {
              depthFirstSearch(w);
           }
        }
}






Here is some working C code for a DFS on a BST..


#include 

typedef struct node
{
  int value;
  int visited;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void treeDFS(mynode *root);


int main(int argc, char* argv[])

  root = NULL;
  
  // Construct the tree..
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  
  // Do a DFS..
  printf("\n\nDFS : ");
  treeDFS(root);
  
  getch();
}

// Function to add a new node to the tree...
mynode *add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->visited = 0;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
     
   return(temp);  
     
}



// DFS..
void treeDFS(mynode *root)
{
    printf("[%d] ", root->value);
    root->visited = 1;
    
    if (root->left)
    {
      if(root->left->visited==0)
      {
        treeDFS(root->left);
      }
    }

    if (root->right)
    {
      if(root->right->visited==0)
      {
        treeDFS(root->right);
      }
    }
}






Breadth First Search


Breadth First Search (BFS) searches the graph one level (one edge away from the starting vertex) at a time. In this respect, it is very similar to the level order traversal that we discussed for trees. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then visit and process all of v's neighbors. Now that we've visited and processed all of v's neighbors, we need to visit and process all of v's neighbors neighbors. So we go to the first neighbor we visited and visit all of its neighbors, then the second neighbor we visited, and so on. We continue this process until we've visited all vertices in the graph. We don't use recursion in a BFS because we don't want to traverse recursively. We want to traverse one level at a time. So imagine that you visit a vertex v, and then you visit all of v's neighbors w. Now you need to visit each w's neighbors. How are you going to remember all of your w's so that you can go back and visit their neighbors? You're already marked and processed all of the w's. How are you going to find each w's neighbors if you don't remember where the w's are? After all, you're not using recursion, so there's no stack to keep track of them. To perform a BFS, we use a queue. Every time we visit vertex w's neighbors, we dequeue w and enqueue w's neighbors. In this way, we can keep track of which neighbors belong to which vertex. This is the same technique that we saw for the level-order traversal of a tree. The only new trick is that we need to makr the verticies, so we don't visit them more than once -- and this isn't even new, since this technique was used for the blobs problem during our discussion of recursion.





public void breadthFirstSearch(vertex v)
{
   Queue q = new Queue();

   v.visited = true;
   q.enQueue(v);

   while( !q.isEmpty() )
   {
       Vertex w = (Vertex)q.deQueue();

       // Print the node.
  
       for(each vertex x adjacent to w)
       {
           if( !x.visited )
           {
              x.visited = true;
              q.enQueue(x);
           }
        }
    }
}




BFS traversal can be used to produce a tree from a graph.


Here is some C code which does a BFS (level order traversal) on a BST...


#include 

typedef struct node
{
  int value;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

add_node(int value);

void levelOrderTraversal(mynode *root);

int main(int argc, char* argv[])

  root = NULL;
  
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  

  printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
  levelOrderTraversal(root);
  
  getch();
}




// Function to add a new node...
add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0}; // Important to initialize!
  int size = 0;
  int queue_pointer = 0;
  
  while(root)
  {
      printf("[%d] ", root->value);

      if(root->left)
      {
        queue[size++] = root->left;
      }

      if(root->right)
      {
        queue[size++] = root->right;
      }
      
      root = queue[queue_pointer++];    
  }
}



Question 19

Write pseudocode to add a new node to a Binary Search Tree (BST)
 


Here is a C code to construct a BST right from scratch...


#include 

typedef struct node
{
  int value;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

add_node(int value);
void postorder(mynode *root);
void inorder(mynode *root);
void preorder(mynode *root);

int main(int argc, char* argv[])

  root = NULL;
  
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  
  printf("\nPreorder    : ");
  preorder(root);
  printf("\n\nPostorder : ");
  postorder(root);
  printf("\n\nInorder   : ");
  inorder(root);

  return(0);
}

// Function to add a new node...
add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
}



void preorder(mynode *root)
{
  if(root)
  {
    printf("[%d] ", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}


void postorder(mynode *root)
{
  if(root)
  {
    postorder(root->left);
    postorder(root->right);
    printf("[%d] ", root->value);
  }
}




void inorder(mynode *root)
{
  if(root)
  {
    inorder(root->left);
    printf("[%d] ", root->value);
    inorder(root->right);
  }
}



Question 20

What is a threaded binary tree?
 


Since traversing the three is the most frequent operation, a method must be devised to improve the speed. This is where Threaded tree comes into picture. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. An extra field called the rthread is used. If rthread is equal to 1, then it means that the right link of the node points to the inorder success. If its equal to 0, then the right link represents an ordinary link connecting the right subtree.


struct node
{
  int value;
  struct node *left;
  struct node *right;
  int rthread;
}



Function to find the inorder successor


mynode *inorder_successor(mynode *x)
{
  mynode *temp;
  
  temp = x->right;
  
  if(x->rthread==1)return(temp);

  while(temp->left!=NULL)temp = temp->left;
  
  return(temp);
}



Function to traverse the threaded tree in inorder


void inorder(mynode *head)
{
   mynode *temp;

   if(head->left==head)
   {
      printf("\nTree is empty!\n");
      return;
   }

   temp = head;

   for(;;)
   {
       temp = inorder_successor(temp);
       if(temp==head)return;
       printf("%d ", temp->value);
   }

}




Inserting toward the left of a node in a threaded binary tree.


void insert(int item, mynode *x)
{
   mynode *temp;
   temp = getnode();
   temp->value = item;
   x->left = temp;
   temp->left=NULL;
   temp->right=x;
   temp->rthread=1;
}



Function to insert towards the right of a node in a threaded binary tree.


void insert_right(int item, mynode *x)
{
   mynode *temp, r;

   temp=getnode();
   temp->info=item;
   r=x->right;
   x->right=temp;
   x->rthread=0;
   temp->left=NULL;
   temp->right=r;
   temp->rthread=1;
}



Function to find the inorder predecessor (for a left threaded binary three)


mynode *inorder_predecessor(mynode *x)
{
     mynode *temp;
  
     temp = x->left;
  
     if(x->lthread==1)return(temp);

     while(temp->right!=NULL)
       temp=temp->right;

     return(temp);
}



 




Test Your Skills Now!
Take a Quiz now
Reviewer Name