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.

If you are preparing for a tech interview, don't forget to check the Interview Study Guides.

Big-Oh English Java Programming

Tips and Solutions for Dell XPS 13 Developer Edition

The Dell XPS 13 Developer Edition comes with Ubuntu 12.04, and even though most of its hardware works perfectly with Ubuntu there are some things that doesn't quite work from the beginning (what a shame).

In this post I present some of the issues that I experienced with this powerful ultrabook and how I solved them.

Bluetooth

At the beginning I couldn't enable the bluetooth but after the first Ubuntu update it worked perfectly.

Additional Tip: if you want to send files from your phone to your computer you should do search and find "Personal File Sharing" in the dash and activate both the checkboxes under "Recieve Files over Bluetooth, as commented by Reza Ghayem in AskUbuntu.

WiFi

By default there are some issues with the stability of WiFi connections. If your WiFi connection is not stable (ie: disconnects and reconnects a lot) you should run the following in a Terminal:

sudo apt-get install linux-generic-lts-quantal

and reboot your computer after that as suggested by Dan Wood in this AskUbuntu post.

Hibernate

Warning: Some people have reported some problems (ruins installation) using this hibernate tip when the Home directory is encrypted. I haven't confirmed this, though.

Although in my case Suspend worked from the beginning, Hibernate didn't so just installing uswusp solves the issue:

sudo apt-get install uswsusp

There are additional instructions suggested here but they weren't necessary. After installing uswsusp you can try hibernating your computing executing in a terminal:

sudo s2disk

If it works then you just have to restart the computer (after waking it up) and check hibernate through the standard options in Ubuntu (right top button-->Hibernate).

And that's it! Just let me know if you have additional hacks needed for Dell XPS 13 Developer Edition or if you had any problem with any of these solutions!

Dell English Linux Tips Troubleshooting Ubuntu