Showing posts with label Binary Tree. Show all posts
Showing posts with label Binary Tree. Show all posts

Saturday, 23 June 2012

Print boundary of a binary tree. Microsoft Interview.


Print boundary (edge nodes or outside frame) of a binary tree

Microsoft Interview (May 2012) 



Problem Statement

Print outside frame of a binary tree anti-clockwise.
1) Print all left most nodes.
2) Print all leaf nodes.
3) Print all right most nodes.

Please note:
  • If a node is a left-most node, then its left child must be a left-most node as well.
  • If its left child does not exist, then its right child will be a left-most node.

 Example:
                                    1000
            500                                                1500
    240                510                    1300
120        300                600                   1320

Output:1000 500 240 120 300 600 1320 1300 1500


Algorithm

1) Print root node if it exist.
2) Print left most edges from top to bottom. If a node is a left-most node, then its left child must be a left-most node but if its left child does not exist, then its right child will be a left-most node.
3) Print leaf nodes - a node whose left and right child both are null it is a leaf node.
4) Print right most edges from bottom to top.
    
If you have a different approach in mind, please share it in the comments section.

 Solution

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

struct node {
    struct node *left;
    struct node *right;
    int data;
};

struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}

void printLeftBoundary(node *root) {

    if(root==NULL) return;
    if(root->left) {
       printf("%d ",root->data);
       printLeftBoundary(root->left);
    }
    else if(root->right) {
       printf("%d ",root->data);
       printLeftBoundary(root->right);
    }
}

void printLeafBoundary(node *root) {

    if(root) {
  
       printLeafBoundary(root->left);
     
       if(root->left==NULL && root->right==NULL)
          printf("%d ",root->data);
        
       printLeafBoundary(root->right);
    }
}

void printRightBoundary(node *root)
{
    if(root==NULL) return;
    if(root->right) {
       printRightBoundary(root->right);
       printf("%d ",root->data);
    }
    else if(root->left) {
       printRightBoundary(root->left);
       printf("%d ",root->data);
    }
}

void printBoundary(node *root)
{
if(root)
    {
        printf("%d ", root->data);
      
        printLeftBoundary(root->left);
      
        printLeafBoundary(root);
      
        printRightBoundary(root->right);
    }
}

int main()
{
    struct node *root=newnode(1000);
    root->left=newnode(500);
    root->right=newnode(1500);
    root->left->right=newnode(510);
    root->left->right->right=newnode(600);  
    root->left->left=newnode(240);
    root->left->left->left=newnode(120);
    root->left->left->right=newnode(300);  
    root->right->left=newnode(1300);
    root->right->left->right=newnode(1320);  
  
    printBoundary(root);
  

    return 0;
}



Time Complexity

PrintLeftBoundary - O(h), where h is height of tree, log(n) nodes on left are visited once
PrintLeafBoundary - O(n), as each node is visited once
PrintRightBoundary - O(h), where h is height of tree, log(n) nodes on right are visited once.

O(n+2h) total time complexity
 


Sunday, 10 June 2012

Check if tree is a BST O(n) code Common Interview Question


Check if tree is a Binary Search Tree or not 

Most Common Interview Question



Problem Statement

Write a program to check if a tree is a Binary Search Tree or not.

Algorithm

While doing in-order traversal, keep track of previous node in a static variable and compare its data with root's (next) data. Plus also check if left subtree and right subtree also follow binary search tree property.

If you have a different approach in mind, please share it in comments section for our readers.

Solution

int isBST(node *root) {

    static int node *prev_node = NULL;
   
    if(root == NULL) return 1;
   
    if(!isBST(root->left))
        return 0;
       
    if(prev_node != NULL && root->data <= prev_node->data)
        return 0;
    prev_node = root;
   
    if(!isBST(root->right))
        return 0;
    
    return 1;       
    
}

Time Complexity

O(n) since we visit each node only once.


If you find this blog somewhat helpful, please give a +1.

Saturday, 9 June 2012

Tree Longest Path: O(n) C code


Longest path between any two nodes of a Binary Tree

Amazon Interview (May 2012)


Problem Statement

Find the length of longest path between any two leaf nodes of a binary tree. Actually leaf nodes are at maximum distance so its okay to say nodes as well as leaf nodes.

Solution 1: 

// O(n*n) code
int longestPath(node *root)
{

   if(root==NULL)
     return 0;

   int left_height=0, right_height=0;
   int left_max=0, right_max=0;
  
   left_height = height(root->left);
   right_height = height(root->right);

   left_max = diameter(root->left);
   right_max = diameter(root->right);

   int temp = max(left_max,right_max);
  
   return max(temp, left_height+right_height);
}

int height(node* root)
{
   if(root == NULL)
       return 0;
   return 1 + max(height(root->left), height(root->right));
}

Solution 2:

 // O(n) code
// In this code we take adv of pointer and calculate the height in same recursion rather than 
// calling height separately as in Solution 1.
int longestPath(node *root, int *h) {

    int left_height=0, right_height=0;
    int left_max=0, right_max=0;
   
    if(root==NULL) {
      *h=0;
      return 0;
    }
   
    left_max=longestPath(root->left,&left_height);
    right_max=longestPath(root->right,&right_height);
   
    *h=max(left_height,right_height)+1;
   
    int temp = max(left_max,right_max);
   
    return max(temp, left_height+right_height);
   
}


If you have a different approach in mind, please share it in comments section for our readers.


Time Complexity:

  1. O(n*n) - For each node (total n nodes) we calculate height which takes further O(n) time.
    So total time complexity O(n*n).
  2. O(n) - We visit each node only once. So time complexity O(n).


If you find this blog somewhat helpful, please give a +1.

Friday, 1 June 2012

GeeksforGeeks- Arbitrary Binary Tree to a tree that holds Children Sum Property problem : C code


Convert an arbitrary binary tree to a tree that hold children sum property



Problem Statement

Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change structure of tree and cannot decrement value of any node)
 

Children Sum Property - For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children.

Algorithm


Traverse given tree in post order to convert it, first change left and right children of node to hold the CSP property and then change the parent node

Let difference between node’s data and children sum be diff.
     diff = sum of node’s children  - node’s data
 
If diff is 0 then you need to do nothing
If diff > 0 then you need to increment the node’s data by diff.
If diff < 0 then you need to increment one child’s data. But we have a choice we can increment either left child or right child, so I choose left child but this changes the children sub property for the left subtree so that also need to be fixed. So we recursively increment the left child. If left child is empty then we recursively call increment() for right child.

Solution

void convertTree(node *root)
{
    if(root == NULL)
        return;
    if(root->left == NULL && root->right == NULL)
        return;
   
    convertTree(root->left);
    convertTree(root->right);
       
    int sum = 0, diff;
    if(root->left != NULL)
        sum += root->left->data;
    if(root->right != NULL)
        sum += root->right->data;
   
    diff = sum - root->data;
   
    if(diff == 0)
        return;
   
    else if(diff > 0)
        root->data += diff;
   
    else
        increment(root, -diff);
}
   
void increment(node *root, int value)
{

    if(root->left != NULL) {
        root->left += value;
        increment(root->left, value);
    }
    else if (root->right != NULL) {
        root->right += value;
        increment(root->right, value);
    }
}

Time Complexity : O(n*n)


// If you find this blog somewhat helpful, please share it.......&.......Keep visiting..:) 

Check for Children Sum Property in a Binary Tree : C code


Check for Children Sum Property in a Binary Tree 



Problem Statement

Given a binary tree, write a function that returns true if the tree satisfies below property.
For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children

Solution

int checkCSP(node * root) {
   
    if(root == NULL)
        return 1;
    if(root->left == NULL && root->right == NULL)
        return 1;
   
    int sum = 0;
    if(root->left != NULL)
        sum += root->left->data;
    if(root->right != NULL)
        sum += root->right->data;
   
    return (root->data == sum) && checkCSP(root->left) && checkCSP(root->right);
   
}


//If you have a different approach in mind, please share it in comments section for our readers. 


Time Complexity : O(n), we are doing a complete traversal of the tree.

Check out the extension of this problem "Convert arbitrary binary tree to a tree that holds Children Sum Property".