Topic on Trees and related Interview Questions

Trees are non linear data structures.There are some examples tree structured hierarchies.

Directory Hierarchies:
In computers, files are stored in directories that form a tree. The top level directory represents the root. It has many sub directories and files. The sub directories would have further set of sub directories.

Organization charts: In a company a number of vice presidents report to a president. Each VP would have a set of general managers, each GM having his/her own set of specific managers and so on.

Biological classifications: 

Starting from living being at the root, such a tree can branch off to mammals,birds, marine life etc.

Tree as a data structure
   A tree is a data structure that is made of nodes and pointers, much like a linked list. The difference between them lies in how they are organized. 

• The top node in the tree is called the root and all other nodes branch off from this one. 
• Every node in the tree can have some number of children. Each child node can in turn be the parent node to its children and so on. 
• Child nodes can have links only from a single parent 
• Any node higher up than the parent is called an ancestor node.
• Nodes having no children are called leaves (Leaf node)
• Any node which is neither a root, nor a leaf is called an interior node. 
• An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.
• The height of a tree is defined to be the length of the longest path from the root to a leaf in that tree( including the path to root) 

Binary Tree

A binary tree is a tree in which each node can have maximum two children.
Thus each node can have no child, one child or two children.
The pointers help us to identify whether it is a left child or a right child.
(or)

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side.

Application of a Binary tree
Before we define any formal algorithms, let us look at one possible application of a binary tree.
Consider a set of numbers: 25,63,13, 72,18,32,59,67.

Suppose we store these numbers in individual nodes of a singly linked list. To search for a particular item we have to go through the list, and maybe we have togo to the end of the list as well. Thus if there were n numbers, our search complexity would be O(n).

Is it because the numbers are not in any particular sequence? Now suppose we order these numbers:
13,18,25,32,59,63,67,72. and store these in another linked list.
What would be the search complexity now? You may be surprised to discover that it is still O(n). You
simply cannot apply binary search on a linked list with O(log n) complexity. You still have to go
through each link to locate a particular number. So a linear linked structure is not helping us at all.

A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>). 

 

The tree shown above is a binary search tree -- the "root" node is a 5, and its left subtree nodes (1, 3, 4) are <= 5, and its right subtree nodes (6, 9) are > 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3. Watch out for the exact wording in the problems -- a "binary search tree" is different from a "binary tree".
The nodes at the bottom edge of the tree have empty subtrees and are called "leaf" nodes (1, 4, 6) while the others are "internal" nodes (3, 5, 9).

Examples of Binary Tree

 

Below are not Binary trees

 

Tree Terminologies
Edges: The arrows from one node to another are called edges
Length of a path:  The length of a path is the number of nodes in the path
Degree of a node : The degree of a node is the number of edges connected to the node.
 or  How many child nodes are connected to that node
Basic property of a binary tree -> Degree of node should not exceed more than 2.

 Level of a node :   Level of root node is 0.
                                Level of any other node in the tree is one more than the level of its parent node.

 

Height of the Tree:  is also called as Depth of the Tree

Height (or Depth) of the tree is equal to max number of levels in a tree.
or It is longest path from root node to Leaf node (or)
The height of a tree is a height of the root.

In the above example, max number of levels are 4  i.e.  Leve1 0,  Leve1 1,  Leve1 2,  Leve1 3,

Height of the Tree = 4  (Level 0 + ... +Level 3) 

                   A
                  /  \
                 1    2        
                / \    \
               3   4    C
                         \
                          D

Height of a tree is number of nodes from root to leaf following the

longest path. So if we have one node (root itself) height=1 

Empty tree: 0 

In the above example, the number of nodes from root node to leaf node is 4

A - 2 - C - D  (Node count = 4)

Depth of a Node:  Depth of Root Node is Zero (0)

Depth of a node is also called as Level of a node.

Depth or level of any node is number of edges from root node to that node. 

or 

Alternatively, we can define the depth of a node as the number of ancestors it has, 

Note that the root is at depth 0, because it has no ancestors;

                   A
                  /  \
                 1    2        
                / \    \
               3   4    C
                         \
                          D 

Depth of Node 3 = Number of ancestors  = Number of edges from root = 2

Depth of Node D = Number of ancestors  = Number of edges from root = 3

Height of a Node:  Height of Leaf Node is Zero (0)

The height of a node is the number of edges from the node to the deepest leaf.

Height of Node 3 = Number of Edges = 0

Height of Node 2 = Number of edges from that Node to Leaf = 2 

 
Size of a Tree: Max Number of nodes in a tree.
         size = number of nodes in a tree.


FULL BINARY TREE:  
A full binary tree is a binary tree in which each node has exactly zero or two children.   
or
A binary tree T is full if each node is either a leaf or possesses exactly two child nodes.   

 
The following conditions should satisfy by a binary tree:

If a full binary tree has i internal nodes:

• no of leaves = i+1
• total no of nodes = 2 * i +1

If a full binary tree has n nodes:

• no of internal nodes = (n-1)/2
• no of leaves = (n+1)/2

If a full binary tree has l leaves:

• total no of nodes = 2 * l -1
• no of internal nodes = l – 1

   

 
How many nodes?
Level 0 : 1 node ( height 1)
Level 1 : 2 nodes (height 2)
Level 3 : 4 nodes (height 3)
Level 3 : 8 nodes (height 4)

Total number of nodes
          n = (2^h) – 1 ( maximum)
          h = log ( n+1)
COMPLETE BINARY TREE:  
A complete binary tree is a binary tree in which every level of the tree  is completely filled except the last level. Also, at the last level, the nodes should be filled from the left most part of the tree. 
The following trees are examples of Complete Binary Trees
    1
  /   \
 2     3
  
       1
    /    \
   2       3
  /
 4

       1
    /    \
   2      3
  /  \    /
 4    5  6

The following trees are examples of Non-Complete Binary Trees
    1
      \
       3
  
       1
    /    \
   2       3
    \     /  \   
     4   5    6

       1
    /    \
   2      3
         /  \
        4    5

Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height 
height of root node is 0.
h = 2^0 + 2^1 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1 

How Recursion Works in Binary Tree:

In this above example, let's find out the size of the tree or number of 

nodes in the tree

 1. Step 1: sizeofTree(root)  
          = sizeofTree(5T)
               |
               --  (node ! = NULL) -> SizeofTree(left) + 1+ SizeofTree(right) -> sizeof(2T) +1 + sizeof(21T)

          = sizeof(2T)
              |
               -> sizeofTree(1T) + 1 + sizeofTree(3T)     

          = sizeof(1T)
               |
               -> sizeofTree(0) + 1 + sizeofTree(0)    

          = if(node == NULL) return 0 => sizeofTree(0) returns 0

          = sizeof(1T) = 0+1+0 = 1 -> Returns to the sizeof(2T).

          similarly -> sizeofTree(3T) 

           |
           -> sizeofTree(0) + 1 + sizeofTree(0)    

          = if(node == NULL) return 0 => sizeofTree(0) returns 0

          = sizeof(1T) = 0+1+0 = 1 -> Returns to the sizeof(2T).

          
          =  Sizeof(2T) = 1+1+1 = 3 returns to sizeof(5T).

        
Similarly sizeof(21T) computes gives 3.

   The total sizeof(2T) +1 + sizeof(21T) -> 3+1+3 = 7. 
 

C PROGRAM for BINARY TREES 

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

#define EXIT 33

/* Basic of TREE struct declaration */ 
struct tree
{
   int data;
   struct tree *left;
   struct tree *right;
};

typedef struct tree TREE;

TREE *root;

TREE *root2;
/*
 *  Create binary Tree
 */
TREE *createBinaryTree()
{
   int info;
   TREE *newTreeNode;

   printf("Enter the Data of Node of a Tree\n");
   scanf("%d", &info);

   newTreeNode = (TREE *)malloc(sizeof(TREE));

   if(newTreeNode == NULL)
   {
      printf("Memory allocation Failure \n");
      return;
   }
   else
   {
      newTreeNode->data    = info;
      newTreeNode->left    = NULL;
      newTreeNode->right  = NULL;
   }
   return newTreeNode;
}

TREE *newNode(int data)
{
   int info;
   TREE *newTreeNode;

   newTreeNode = (TREE *)malloc(sizeof(TREE));

   if(newTreeNode == NULL)
   {
      printf("Memory allocation Failure \n");
      return;
   }
   else
   {
      newTreeNode->data    = data;
      newTreeNode->left    = NULL;
      newTreeNode->right  = NULL;
   }
   return newTreeNode;
}

/*
 * insertBinaryTree() -> Previous Node Place Important Role
 */
void insertBinaryTree()
{
  TREE *newNode = NULL, *temp = NULL, *prevNode= NULL;
  
  /* Create New Node */
  newNode = createBinaryTree();

 if(root == NULL)
 {
  root = newNode;
  return;
 }
 temp = root;
  
 while(temp != NULL)
 {
    if(newNode->data <= temp->data)
    {
       /*Core Logic */
       prevNode = temp;
       temp = temp->left;
    }
    else 
    {
      if(newNode->data > temp->data)
      {
         prevNode = temp;
         temp = temp->right;
      }
    }
  }
  /* Left */
  if(newNode->data <= prevNode->data)
  {
     prevNode->left = newNode;
  }
  else
  {
     prevNode->right = newNode;
  }
}
 
/*
 * insertBinaryTreeWithRecursion()
 */
/* In the case of Recursion Child nodes return to the parent */
TREE *insertBinaryTreeWithRecursion(TREE *root, TREE *newNode)
{
   static int i= 0;
   if(root == NULL)
   {
      root = newNode;
      return root;
   }
   else
   {
      if(newNode->data <= root->data)
      {
        root->left  = insertBinaryTreeWithRecursion(root->left, newNode);
      }
      else
      {  
        root->right = insertBinaryTreeWithRecursion(root->right, newNode);
      }
    printf(" The Static Count : %d\n", ++i);
    return root;
   }
}

/*
 * printPreorderTree()
 */
void printPreorderTree(TREE *temp)
{
  if(temp!= NULL)
  {
     printf("The Data:  %d\n", temp->data);
     printPreorderTree(temp->left);
     printPreorderTree(temp->right);
  }
}
/*
 * printPostorderTree()
 */
void printPostorderTree(TREE *temp)
{
  if(temp!= NULL)
  {
     printPostorderTree(temp->left);
     printPostorderTree(temp->right);
     printf("The Data:  %d\n", temp->data);
  }
}
/*
 * printInorderTree()
 */
void printInorderTree(TREE *temp)
{
  if(temp!= NULL)
  {
     printInorderTree(temp->left);
     printf("The Data:  %d\n", temp->data);
     printInorderTree(temp->right);
  }
}

/* Size Of Tree */
int sizeOfTree(TREE *node)
{
   if(node!=NULL)
   {
      return(sizeOfTree(node->left) +1 + sizeOfTree(node->right));
   }
   else // No Nodes
   {
      return 0;
   }
} 
/* Binary Search ( Lookup) in the TREE */ 
int binarySearchLookup(TREE *node,  int data)
{
   while(node != NULL)
   {
      if(node->data == data)
      {
        return 1;
      }
      else if(data < node->data)
      {
         node = node->left;
      }
      else
      {
         node = node->right;
      }
   }
   return 0;
}
/* Min Value of Binary Tree lies in left*/
void minValueOfBinaryTree(TREE *node)
{
  while(node->left != NULL)
  {
    node = node->left;
  }
  printf(" The Min Value of Binary Tree :%d\n", node->data);   
}

/* Max Value of Binary Tree lies in the right */
void maxValueOfBinaryTree(TREE *node)
{
  while(node->right != NULL)
  {
    node = node->right;
  }
  printf(" The Max Value of Binary Tree :%d\n", node->data);   
}

/*
 * maxDepth of a tree -- the number of nodes along
 * the longest path from the root node down 
 */
int maxDepthOfTree(TREE *node)
{
  int left = 0, right= 0;
  if(node == NULL)
  {
    return 0;
  }
  else
  {
     left  = maxDepthOfTree(node->left);
     right = maxDepthOfTree(node->right);

     if(left > right)
      return (left +1);
     else
       return (right +1);
   }
}

/*
 Change a tree so that the roles of the
 left and right pointers are swapped at every node.

 So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/ 

TREE *mirrorOfTree(TREE *node)
{
   TREE *temp = NULL;
   
   if(node ==NULL)
   {
      return 0;
   }
   else
   {
      mirrorOfTree(node->left);
      mirrorOfTree(node->right);
      
      /* swap the pointers in this node  */
     temp = node->left;
     node->left = node->right;
     node->right = temp;  
   }
  
  return node;
}
/*
 For each node in a binary search tree,
 create a new duplicate node, and insert
 the duplicate as the left child of the original node.
 The resulting tree should still be a binary search tree.

 So the tree...
    2
   / \
  1   3

 Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1 
*/

TREE *doubleTheTree(TREE *node)
{
  TREE *oldLeft = NULL;

   if(node == NULL)
     return;

   doubleTheTree(node->left);
   doubleTheTree(node->right);

   // duplicate this node to its left
   oldLeft = node->left;
   node->left = newNode(node->data);
   node->left->left = oldLeft; 
 
   return node;
}
/*
 Given two trees, return true if they are
 structurally identical.
*/ 
int sameTreeOrNot(TREE *a , TREE *b)
{
  // 1. both empty -> true
  if (a==NULL && b==NULL) return(1);

  // 2. both non-empty -> compare them
  else if (a!=NULL && b!=NULL) {
    return(
      a->data == b->data &&
      sameTreeOrNot(a->left, b->left) &&
      sameTreeOrNot(a->right, b->right)
    );
  }
  // 3. one empty, one not -> false
  else return(0); 
}
/*
 * Count Leaf Nodes
 */
int countLeafNodes(TREE *node)
{
   static int count;
  
   if(node == NULL)
   {
     return 0;
   }
   else if(node!=NULL)
   {
      countLeafNodes(node->left);
      
      if(node->left == NULL && node->right==NULL)
      { 
        // This is a leaf!
        count++;
      }

      countLeafNodes(node->right);
   }
   return count;
}

/* Inorder Successor 
 *
 */
 /* Case 1:
 * If right subtree of given node is not NULL, then succ lies in right subtree. 
 * Do following.
 * Go to right subtree and return the node with minimum key value in right subtree.
 * 
 * If right sbtree of given node is NULL, then succ is one of the ancestors
 * Travel down the tree, if a node’s data is greater than root’s data 
 * then go right side, otherwise go to left side.
 */
TREE *inorderSucessor(TREE *node, TREE *givenNode)
{
    TREE *succ = NULL;

   // step 1 of the above algorithm
    if( givenNode->right != NULL )
    {
        //or return( minValueOfBinaryTree(givenNode->right));
        minValueOfBinaryTree(givenNode->right);
        return 0;
    }
    // Start from root and search for successor down the tree
    while (node != NULL)
    {
        if (givenNode->data < node->data)
        {
            succ = node;
            node = node->left;
        }
        else if (givenNode->data > node->data)
            givenNode = givenNode->right;
        else
           break;
    }
 
    return succ;
}
 /* 
  * Main Function()
 */
int main()
{
   int ch, found, totalNodes, depth; TREE *temp = NULL;
   do
   {
      printf(" Enter the choice \n");
      printf(" 1. Insert with out Recursion \n");
      printf(" 2. Insert with Recursion \n");
      printf(" 3. Size of the Tree (Count the Number of Nodes)\n");
      printf(" 4. Binary Search or Lookup in the Tree \n");
      printf(" 5. Find the Minimum value of tree \n");
      printf(" 6. Find the Maximum value of tree \n");
      printf(" 7. Find the Maximum Depth of the tree (Number of Nodes"
                  "from Root to Leaf Node \n");
      printf(" 8. Mirror the Tree  \n");
      printf(" 9. Double the Tree  \n");
      printf(" 10. Same Trees or Not \n");
      printf(" 11. Count Leaf Nodes \n");
      printf(" 12. Inorder Sucessor of a Binary Tree \n");
      printf(" 13. Print the Tree using Pre-Order Traversal\n");
      printf(" 14. Print the Tree using In-Order Traversal\n");
      printf(" 15. Print the Tree using Post-Order Traversal\n");
      printf(" 33. EXIT \n");
      scanf("%d", &ch);      
      switch(ch)
      {
         case 1: insertBinaryTree();
         break;
         case 2: 
         { 
           TREE *newNode = NULL;
           newNode = createBinaryTree();
           root = insertBinaryTreeWithRecursion(root, newNode);
         }
         break;
         case 3: 
           totalNodes = sizeOfTree(root);
           printf("The Total Number of Nodes %d\n", totalNodes);
         break;
         case 4:
         {
           printf(" Enter the Data to be search in binary tree \n");
           scanf("%d", &ch);
           found =binarySearchLookup(root, ch);
           if(found == 1)
              printf(" Data is found in the Tree \n");
           else
              printf(" Data is not found in the Tree \n");
          }
         case 5:
           minValueOfBinaryTree(root);
         break;
         case 6:
           maxValueOfBinaryTree(root);
         break;
         case 7:
          {
             depth = maxDepthOfTree(root);
             printf(" The Depth of the Tree : %d\n", depth);
          }
         break;

         case 8:  root2 = mirrorOfTree(root);
                  printf(" Print the Mirror Tree using Pre-Order \n");
                  printPreorderTree(root2);
         break;

         case 9:  root2 = doubleTheTree(root);
                  printf(" Print the Mirror Tree using Pre-Order \n");
                  printPreorderTree(root2);
         break;

         case 10: 
            {
                if( sameTreeOrNot(root, root))
                {
                   printf(" Trees are Equal \n");
                }
                else
                {
                   printf(" Trees are not equal \n");
                }
            }
         break;
        
         case 11: totalNodes  = countLeafNodes(root);
                printf(" The Number of Leaf Nodes are :%d\n", totalNodes); 
         break;
         case 12:
            /*  Pointing temp to some node in a given tree */
            temp = root->left->right; 
            root2 = inorderSucessor(root, temp);
            if(root2)
            { 
              printf(" First The Inorder Sucessor for %d is :%d\n", temp->data, 
                root2->data);
            }
            temp = root->left; 
            root2 = inorderSucessor(root, temp);
            if (root2)
            {
              printf(" First The Inorder Sucessor for %d is :%d\n", temp->data, 
                root2->data);
            }
         break;
         case 13: printPreorderTree(root);
         break;
         
         case 14: printInorderTree(root);
         break;

         case 15: printPostorderTree(root);
         break;

         default:
            printf("Invalid choice \n");
            break;
      }
   
   }while(ch!=EXIT);

}