Largest Binary Search Tree (BST), by Apple

Here is today's problem from Daily Coding Problem:

This problem was asked by Apple.

Given a tree, find the largest tree/subtree that is a BST.

Given a tree, return the size of the largest tree/subtree that is a BST.

Take a look at the tree below. Every node by itself is a BST of course, but I have highlighted some other BSTs in this tree. The largest one has double lines covering it, and has 5 nodes:

I first tried one approach de-serializing using in-order traversal so that I'd end up with a sorted list, and from there look at the BSTs, but it really doesn't quite work. An idea that worked was to do a post-order traversal using the following logic:

• The function returns the largest BST with the current node as the root
• Call for the left (a)
• Call for the right (b)
• The minimum number for the current node should be 1
• But if the left node is smaller, add it (from (a))
• But if the right node is larger, add it (from (b))
• Check whether the current value is greater than the max (and set max accordingly)
• Return the current

Running against the input above does return 5:

Code is down below and on GitHub, here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem12162018.cs

Cheers, Marcelo

public int LargestBST(Tree tree)
{
 int max = 0;
 LargestBST(tree, ref max);
 return max;
}

private int LargestBST(Tree tree, ref int max)
{
 if (tree == null) return 0;

 int maxLeft = LargestBST(tree.left, ref max);
 int maxRight = LargestBST(tree.right, ref max);

 int current = 1;
 if (tree.left != null && tree.val > tree.left.val)
  current += maxLeft;
 if (tree.right != null && tree.val <= tree.right.val)
  current += maxRight;

 max = (current > max) ? current : max;
 return current;
}