Friday, September 20, 2013

Find Largest Binary Search Tree in a Tree: Java Solution

The question is simple and fair common:

Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree. (From: GeeksForGeeks)

Additionally, I'll be returning the root node for the BST. In this case the BST would have to include all its children (i.e.: it must be a BST from a specific node to the leaves).

Algorithm

To find the largest BST in a tree there are different options to traverse the tree: we could take an top-down approach or a bottom-up.

Top-Down

The top-down approach require us to check at each node from the root if the tree starting at that node is a BST. This makes us traverse multiple times the tree to find the bst. Although it stops as soon as it find a BST because it will be the largest. This solution has a time complexity of O(n^2) in worst-case (degenerated tree into list) or O(nLogn) (balanced tree)
 where n is the number of nodes in the tree.

Bottom-Up

A better approach will be bottom-up where we check from the bottom of the tree the nodes to check if the trees created are BST. This makes the evaluation of a BST in O(1) for each node, although we still have to traverse the tree completely, so this approach has a time complexity of O(n) (in fact we have to traverse the tree twice because to get to the bottom nodes we must traverse from the root and then again from the bottom to the top).

Given the implementation is recursive, this has a space complexity of O(n). 

Implementation

Below is my Java proposed solution. For a complete solution (including testing, full comments and printing) check this.




2 comments:

  1. Your algorithm has some bug. It doesn't work on the following tree:
    treeA = new Integer[]{10, 5, 15, 1, 8, 13, 7, null, null, null, null, null, 14, null, null};

    ReplyDelete
    Replies
    1. Hi Dong, how are you loading that tree to a TreeNode (in-order, pre-order, post-order)?

      Delete