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.

	public class LargestBst{
	public static class TreeNode {
	int value;
	TreeNode left;
	TreeNode right;
	}
	public static class TreeNodeHelper {
	TreeNode node;
	int nodes;
	Integer maxValue;
	Integer minValue;
	boolean isBST;
	public TreeNodeHelper() {}
	public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {
	this.node = node;
	this.nodes = nodes;
	this.maxValue = maxValue;
	this.minValue = minValue;
	this.isBST = isBST;
	}
	}
	public static TreeNodeHelper getLargestBST(TreeNode tree) {
	if (tree == null) {
	return new TreeNodeHelper(null, 0, null, null, false);
	}
	if (tree.left == null && tree.right == null) {
	TreeNodeHelper helper = new TreeNodeHelper(tree, 1, tree.value, tree.value, true);
	return helper;
	} else {
	TreeNodeHelper leftBst = getLargestBST(tree.left);
	TreeNodeHelper rightBst = getLargestBST(tree.right);
	if (!(rightBst.isBST && rightBst.minValue > tree.value)) {
	rightBst.isBST = false;
	}
	if (!(leftBst.isBST && leftBst.maxValue < tree.value)) {
	leftBst.isBST = false;
	}
	if (leftBst.isBST && rightBst.isBST) {
	return new TreeNodeHelper(tree, rightBst.nodes + leftBst.nodes + 1, rightBst.maxValue, leftBst.minValue, true);
	} else if (tree.left == null && rightBst.isBST) {
	return new TreeNodeHelper(tree, ++rightBst.nodes, rightBst.maxValue, tree.value, true);
	} else if (tree.right == null && leftBst.isBST) {
	return new TreeNodeHelper(tree, ++leftBst.nodes, tree.value, leftBst.minValue, true);
	} else {
	return leftBst.nodes >= rightBst.nodes ? leftBst : rightBst;
	}
	}
	}
	}

view raw LargestBst.java hosted with ❤ by GitHub

Cvielma

Author

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 .