Largest BST Subtree

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #binarytree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:

A subtree must include all of its descendants.

Example:

Input: [10,5,15,1,8,null,7] 10 / \ 5 15 / \ \ 1 8 7 Output: 3 Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Follow up:

Can you figure out ways to solve it with O(n) time complexity?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

**General Thinkings:**

**Key Observations:**

**Walk Through Testdata**

// https://code.dennyzhang.com/largest-bst-subtree