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.
If you are preparing for a tech interview, don't forget to check the Interview Study Guides.
I'm a software developer, with main interest in SOA, Web and Mobile applications design and development. I'm also interested in Travel, Politics, Photography and Volunteering.
"We are what we repeatedly do.Excellence, then, is not an act, but a habit." (Aristotle) is my motto .
Your algorithm has some bug. It doesn't work on the following tree:
ReplyDeletetreeA = new Integer[]{10, 5, 15, 1, 8, 13, 7, null, null, null, null, null, 14, null, null};
Hi Dong, how are you loading that tree to a TreeNode (in-order, pre-order, post-order)?
DeleteThis is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. recover money lost to binary options
ReplyDeleteInteresting problem on Binary Search tree. Knowledge of data structures and algorithms could be immensely helpful to build solid programming skills. Thank you for sharing this educational post. Great blog.
ReplyDelete