Thursday, January 5, 2012

Interview Questions: 4. Tress


Tree

Problem - 1: Implement "Binary Search" in less than two comparison?
BinarySearch(root, key):
    if  root == NULL then
        return root

    res = Root->Data - Key
    if res == 0 then
            return root

    idx = (res >> (sizeof(Key) - 1)) & 1 //GET MSB which is 1 for -ve
    Son[0] = Root -> Left;
    Son[1] = Root -> Right;
    return BinSearch(Son[idx], Key);

Problem - 2: 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

void doubleTree(struct node* node) { 
  struct node* oldLeft;

  if (node==NULL) return;
  // do the subtrees
  doubleTree(node->left);
  doubleTree(node->right);
  // duplicate this node to its left 
  oldLeft = node->left; 
  node->left = newNode(node->data); 
  node->left->left = oldLeft; 

 

Problem - 3: Given two trees, return true if they are structurally identical.

int sameTree(struct node* a, struct node* b) { 
  // 1. both empty -> true 
  if (a==NULL && b==NULL) return(true);
  // 2. both non-empty -> compare them 

  else if (a!=NULL && b!=NULL) { 
    return( 
      a->data == b->data && 
      sameTree(a->left, b->left) && 
      sameTree(a->right, b->right) 
    ); 
  } 
  // 3. one empty, one not -> false 
  else return(false); 
}   

Problem - 4:  For the key values 1...numKeys, how many structurally unique  binary search trees are possible that store those keys.
Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.

int countTrees(int numKeys) {

  if (numKeys <=1) {
    return(1);
  }
  else {
    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;
    for (root=1; root<=numKeys; root++) {
      left = countTrees(root - 1);
      right = countTrees(numKeys - root);
      // number of possible trees with this root == left*right
      sum += left*right;
    }
    return(sum); 
  } 


Problem - 5:  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

void mirror(struct node* node) { 
  if (node==NULL) { 
    return; 
  } 
  else { 
    struct node* temp;

    // do the subtrees
    mirror(node->left);
    mirror(node->right);
    // swap the pointers in this node 
    temp = node->left; 
    node->left = node->right; 
    node->right = temp; 
  } 


Problem  - 6: Given a binary tree, print out all of its root-to-leaf  paths, one per line. Uses a recursive helper to do the work.
void printPaths(struct node* node) { 
  int path[1000];

  printPathsRecur(node, path, 0);
}
/*
 Recursive helper function -- given a node, and an array containing
 the path from the root node up to but not including this node,
 print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
  if (node==NULL) return;
  // append this node to the path array
  path[pathLen] = node->data;
  pathLen++;
  // it's a leaf, so print the path that led to here
  if (node->left==NULL && node->right==NULL) {
    printArray(path, pathLen);
  }
  else {
  // otherwise try both subtrees
    printPathsRecur(node->left, path, pathLen);
    printPathsRecur(node->right, path, pathLen);
  }
}
// Utility that prints out an array on a line. 
void printArray(int ints[], int len) { 
  int i; 
  for (i=0; i
    printf("%d ", ints[i]); 
  } 
  printf("\n"); 


Problem - 7:  Given a tree and a sum, return true if there is a path from the root  down to a leaf, such that adding up all the values along the path equals the given sum.
 Strategy: subtract the node value from the sum when recurring down,
 and check to see if the sum is 0 when you run out of tree. 


int hasPathSum(struct node* node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == NULL) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node->data; 
    return(hasPathSum(node->left, subSum) || 
           hasPathSum(node->right, subSum)); 
  } 
}


Problem - 8: Implement "level order search" for "Binary Tree"?
This problem is same as "breadth first search" for "Binary Tree".
LevelOrder(Root):
     Queue q
    EnQueue(q,Root)
    Loop if (q is not empty)
        Node t = deQueue(q)
        Visit(t)
        if (it's left child is not NULL) then
            EnQueue(leftChild)
        if (it's right child is not NULL) then
            EnQueue(rightChild)
     EndLoopProblem - 9: Find Leaf node in a tree
FindLeafNodes(Tree *root)
{
if (root->left == NULL && root->right == NULL)
     return 1;
else
 return (FindLeafNodes(root->left) + FindLeafNodes(root->right))
}

Problem - 10:  Height of a tree
#define max(x,y) ((x)>(y)?(x):(y))
int height(Tree T)
{
    if(!T)
        return -1;
    else
        return (1 + max(height(T->left), height(T->right)))
}

Problem - 11: No of nodes in a tree
int CountElements( Tree T )
{
    if(!T)
        return 0;
    else
        return (1 + CountElements(T->left) + CountElements(T->right));
}


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

Tree findMin( Tree T) // Recursively finding min element
{
    if( !T )
        return NULL;
    else if( !T->left )
        return T;
    else
        return findMin( T->left );
}

Tree DeleteTree( int x, Tree T) // To Delete whole tree recursively
{
    if(!T)
    {
        DeleteTree(T->left);
        DeleteTree(T->right);
        free(T);
    }
    return NULL;
}

Tree DeleteNode( int x, Tree T ) // To Delete a Node with element x
{
    Tree tmp;
    if(!T)
        return NULL;
    else if( x < T->element )
        T->left = DeleteNode( x, T->left );
    else if( x > T->element )
        T->right = DeleteNode( x, T->right );
    else if( T->left && T->right )
    {
        tmp = findMin( T-> right );
        T->element = tmp->element;
        T->right = DeleteNode( T->element, T->right );
    }
    else
    {
        tmp = T;
        if( T->left )
            T = T->left;
        else if( T->right )
            T = T->right;
        free(tmp);
    }
}

Problem - 13: Write a C program to compute the maximum depth in a tree?
int maxDepth(struct node* node)
{
  if (node==NULL)
  {
    return(0);
  }
  else
  {
    int leftDepth  = maxDepth(node->left);
    int rightDepth = maxDepth(node->right);
    if (leftDepth > rightDepth) return(leftDepth+1);
    else return(rightDepth+1);
  }
}
Problem - 14: Function to add a new value to a Binary Search Tree
add(int value)
{
  mynode *temp, *prev, *cur;
  
  temp = malloc(sizeof(mynode));
  temp->value = value;
  temp->left  = NULL;
  temp->right = NULL;

  if(root == NULL)
  {
    root = temp;
  }
  else
  {
    prev = NULL;
    cur  = root;

    while(cur)
    {
      prev = cur;
      cur  = (value < cur->value)? cur->left : cur->right;
    }
  
    if(value > prev->value)
       prev->right = temp;
    else
       prev->left  = temp;
  }
}



Problem - 15: Tree Traversal
Preorder Recursive:
void preorder(mynode *root)
{
  if(root)
  {
    printf("[%d] ", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

Preorder Iterative:
void iterativePreorder(mynode *root)
{
  mynode *save[100];
  int top = 0;

  if (root == NULL)
  {
    return;
  }
  
  save[top++] = root;
  while (top != 0)
  {
    root = save[--top];

    printf("[%d] ", root->value);

    if (root->right != NULL)
      save[top++] = root->right;
    if (root->left != NULL)
      save[top++] = root->left;
  }
}

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

Postorder Iterative:
void iterativePostorder(mynode *root)
{
  struct
  {
    mynode *node;
    unsigned vleft :1;   // Visited left?
    unsigned vright :1;  // Visited right?
  }save[100];
  
  int top = 0;
  
  save[top++].node = root;

  while ( top != 0 )
  {
      /* Move to the left subtree if present and not visited */
      if(root->left != NULL && !save[top].vleft)
      {
          save[top].vleft = 1;
          save[top++].node = root;  
          root = root->left;
          continue;
      }

      /* Move to the right subtree if present and not visited */
      if(root->right != NULL && !save[top].vright )
      {
          save[top].vright = 1;
          save[top++].node = root;
          root = root->right;
          continue;
      }
    
      printf("[%d] ", root->value);

      /* Clean up the stack */
      save[top].vleft = 0;
      save[top].vright = 0;

      /* Move up */
      root = save[--top].node;
   }
}


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


Inorder Iterative :
void iterativeInorder (mynode *root)
{
  mynode *save[100];
  int top = 0;

  while(root != NULL)
  {
      while (root != NULL)
      {
           if (root->right != NULL)
           {
             save[top++] = root->right;
           }
           save[top++] = root;
           root = root->left;
      }
    
      root = save[--top];
      while(top != 0 && root->right == NULL)
      {
          printf("[%d] ", root->value);
          root = save[--top];
      }
    
      printf("[%d] ", root->value);
      root = (top != 0) ? save[--top] : (mynode *) NULL;
  }
}
Problem - 16: A binary tree contain integer values (both positive and negative) in its data field. Given a number N, find a path from root to leaf which sums to N.

Do iterative pre-order traversal, and keeping tab of sum of elements, we can easily determine if sum of elements from root to any of the leaves is equals to N.
bool ContainsSum(btree *root, int N)
{
if(!root)
return(N == 0)
else{
int remsum = N - root->value;
return((ContainsSum(root->left, remsum)) || (ContainsSum(root->right, remsum)));
}


Problem - 17:  Determine the largest common subtree (structurally) of two given binary trees T1 and T2, that is, the largest subtree of T1 that is structurally identical to a subtree in T2. 
A .Contents of the nodes are irrelevant;
B. Content matters...
A. We will have to modify the inorder tree traversal and put leaf as L and all inner node as p.....so after doing inorder traversal we will get the pattern interrms of L,P,(,) so find the longest common substring among the two trees traversals..this the one common structure.......


Problem - 18:  Given a binary tree with the following node structure
struct node
{
//data
//pointer to left subtree
//pointer to right subtree
//pointer to sibling

};
The sibling pointers are NULL for all the nodes.Make the sibling pointers point to their respective nodes in O(n)time complexity

Nodes from same parent called siblings,If such a tree is given 2's sibling should point to 3 4's to 5,  6's to 7
1. Do BFS level order traversal
2.  keeping a marker to mark the end of a 'level' - Here is is 'NULL'
3. Make a link with sblings

void link(node* root)
 {
queue q;
node* cur = root;
if(root == NULL)
    return;
q.push(root);
q.push(NULL);
while(Q.empty() == false)
{
    root = Q.pop();
    if(Q.empty() == false && root != NULL)
    {
        root.sibling = Q.front();
    }
    if(root)
    {
     if (cur->left) q.push(cur->left);
     if (cur->right) q.push(cur->right);
     // since it is binary tree.. add marker
     q.push(NULL);
    }
}

Problem -  19: Find the inorder successor and predecessor  from a BST.
struct node FindSuccessor(struct node X)
{
if (X.right != NULL)

{
return FindMinimumInBST(X.right);
}
Y = X.parent;
while ((Y != NULL) && (X == Y.right))

{
X = Y;
Y = Y.parent;
}
return Y ;
}

Problem -  20: Find two nodes in BST such that there sum is equal to X
Approach -1
1. Storing inorder in and array of n (and taking 2 pointers j=0,k=n-1)
if(a[j]+a[k]>sum)
k--;
else if ( a[j]+a[k]==sum) return (j,k);
else j++;
Time complexity : O(n )
Space complexity : O(n)


Approach -2
a) Find the min element in the BST, say 'y'. Time complexity : O(log n  )
b) z=x-y
c) do a binary search for z in BST. If it exists , here goes a pair.
d) Find the successor of y. 
e) repeat steps b to d.
Total Time complexity : O(n log n  )
Total Space complexity : O(1), constant


Approach -3
a- Take one pointer pointing to minimum of BST. Time complexity : O(log n  )
b - Take one pointer pointing to maximum of BST. Time complexity : O(log n  )
c - If the sum is greater than SUM then go to predecessor of maximum node.
d - Else if sum is less than SUM then go to successor of minimum node.
while(max->data>min->data)
{
if(max->data+min->data == sum)
    return(1);
else if(max->data+min->data>sum)
    max = inorderpredecessor(max);
else
    min = inordersucessor(min);
}
Problem -  21: Find common ancestor in a binary tree in less than O(n log n) in constant space?
Common Ancestor for BST:
Node getLCA_BST(Node root, Node x, Node y):
    Node curr = root
    while !(x < curr && curr < y): // x.value < curr.value
        if curr < x && curr < y:
            curr = curr.right
        else: //x < curr && y < curr
            curr = curr.left
    return curr // assume x and y are in the tree

 
Common Ancestor for Binary Tree:
class Node:
    int value
    Node left
    Node right
    Node parent

class ListNode:
    Node value //Node is Binary Tree node
    ListNode next

Node getLCA_BT(Node root, Node x, Node y):
    
ListNode lx = getPath(x) // Get list of path
    
ListNode ly = getPath(y) // Get list of path
    return getLCAFromPaths(lx, ly) // find largest match
 
ListNode getPath(Node n):
    ListNode ln = null 

    ListNode after = null
    while (n != null):
        
ln = new ListNode()
        ln.value = n
        ln.next = after
        after = ln
        n = n.parent
    return ln
Node getLCAFromPaths(ListNode lx, ListNode ly):
    Node lca = null
    while (lx.value == ly.value): // lx.value.value
        lca = lx.value //or ly.value
        lx = lx.next
        ly = ly.next
    return lca


Problem - 22: Write a function that, given a binary search tree and a value, will find the next biggest node value in the tree
node* NextBigNode(node* root, int val)
{
if(!root)
    return NULL;
node* nextBig = NULL;
node* cur = root;
while(cur)
{
// If value at current node is GREATER than value, then current could be the potential candidate for nextBig
// Go to the left subtree of current to see if there is another potential candidate for nextBig
if(cur->data > val)

{
nextBig = cur;
cur = cur-> left;
}
// If value at current node is LESS than value, then
// Go to the right subtree of current to see if there is another potential candidate for nextBig
else
{
cur = cur->right;
}
}
return nextBig;
}

Problem  - 23: Given a binary tree, write a program to find the maximum number and print its path from the root.

int maxsofar, maxpos; //global variables
Inorder(node *n, int position)
{
    Inorder(n->left, position*2);
        if(n->data > maxsofar)
            {
            maxsofar = n->data;
            maxpos = position;
            }
    Inorder(n->right, position*2 + 1);
}
By the end of this traversal, you'll have the maximum value in "maxsofar", and the position encoded in an integer "maxpos".
If you don't have parent pointer support in tree node structure, You can print the path like below - 

suppose the maxpos is 23, 
1<-2<-5<-11<-23/2
root->left->right->right->right 
Now to print the path of max value  -
1. Array[(maxpos/2)+1]
2. i = 0
3. Loop while (maxpos > 1)
        {
         maxpos =/2
         Array[i++] = maxpos
        }
4. while (--i >= 0)
    {
    print (root->data)
    if (i %2 == 0)
        root = root->left;
    else
        root = root->right
    }

Problem -24: Construct a "Doubly Link List" form a given "Tree".
void TreeToDlinklist(Tree* pNode):    {    Tree* pWalk;
    if (pNode != NULL)
        {
        TreeToDlinklist(pNode->pLeft);
        pWalk = node->pRight;
        AppendToList(pNode);
        TreeToDlinklist(pWalk);
        }
    }

No comments:

Post a Comment