RSS

Binary Search Tree in Binary Tree

13 Aug

Given a binary tree, find the largest binary SEARCH tree in this binary tree.

When I mean largest, the tree with maximum number of nodes. And the binary search tree should be a sub-tree in the given binary tree.

Note: Not every binary tree is a binary search tree 😛

Advertisements
 
8 Comments

Posted by on August 13, 2010 in Algorithms

 

Tags: , ,

8 responses to “Binary Search Tree in Binary Tree

  1. Name

    August 13, 2010 at 1:25 pm

    any restrictions on running time of algo?
    Worst case O(n2) might to be run isBST on each node from root to leaves..and the first instance of isBST returning true would be our tree right?

     
  2. ranganathg

    August 13, 2010 at 2:12 pm

    Try making it better. The better the complexity the better it is 🙂
    Can we make it in O(n). where n is the number of the nodes in the given “binary tree”.

     
  3. Name

    August 13, 2010 at 5:03 pm

    Hmm…In that case we may need to use extra space..and that standard solution of inorder traversal and finding max sorted subarray in it will help us…

     
  4. ranganathg

    August 13, 2010 at 6:28 pm

    Can you explain a bit clear… find the max sorted array would not help… consider the example
    7
    / \
    5 6
    / /
    3 10

    max sorted array in order traversal is 3 5 7 10, but this is not the answer.

     
  5. Name

    August 16, 2010 at 7:36 pm

    hmm…yaa..totally missed that….thanks for correcting…
    need more thought (atleast for me)

     
  6. pushparaj

    January 20, 2011 at 10:32 am

    global list;

    int fun(treenode node)
    {

    if(node == NULL)
    { return 0;
    }

    a = fun(node.left);
    b= fun(node.right);

    if( (a >=0) && (b >=0))
    {
    if(node.left == NULL)
    {
    if(node.right == NULL)
    {
    list.add(node, 1);
    return 1;
    }

    else if(getfirst_node_inorder_traversal(node.right).value > = node.value)
    {
    list.add(b+1+a , node);
    return b+a+1;//a will be zero as left is null
    }

    else
    return -1;
    }

    else if(node.right == NULL)
    {

    if(getlast_node_inorder_traversal(node.left).value = node.value) && (getlast_node_inorder_traversal(node.left).value < = node.value) )
    {
    list.add(a+b+1,node);
    return a+b+1;

    }

    else
    return -1;

    }

    else
    {
    return -1;
    }
    }//end of fun

    // Now from the list get the pair whose count is greater than all elements in the list. The corresponding node is the maximum binary search tree that we are looking.

     
  7. pushparaj

    January 20, 2011 at 10:33 am

    The complexity for the above one will be O(n). where n is the number of elements present in the binary tree.

     
  8. ranganathg

    January 20, 2011 at 12:40 pm

    Just a rough glance says that this is not O(n) -> It would be O(nlogn)
    And I havent verified your algo. Will do this in a spare time

     

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: