Problem

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.

Examples

Example 1:

1
2
3
4
5

    10
    / \
  [5]  15
  / \   \
[1] [8]   7

1
2
3

Input: root = [10,5,15,1,8,null,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.

Solution

Method 1 - Using Post-order traversal

To solve the problem of finding the largest subtree which is a Binary Search Tree (BST) in a given binary tree, we need to traverse the tree and validate the BST properties for each subtree. We can achieve this using a post-order traversal (left-right-root) to ensure that we can validate each subtree starting from the leaves up to the root.

Approach

  1. Post-order Traversal: Use a post-order traversal to validate each subtree and compute the size of the largest BST valid subtree.
  2. Validation of BST: For each node, check if the subtree rooted at that node is a BST by comparing node values with the min and max values from its subtrees.
  3. Tracking Information: During the traversal, track:
    • The size of the largest BST subtree.
    • The minimum and maximum values in the subtree.
    • Whether the subtree is a valid BST.

Data Structure Definitions:

  • We will define a helper class to store the necessary information for each subtree:
    • Size of the subtree.
    • Minimum value in the subtree.
    • Maximum value in the subtree.
    • Whether the subtree is a BST.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Solution {
    static class SubtreeInfo {
        int size;
        int minVal;
        int maxVal;
        boolean isBST;

        SubtreeInfo(int size, int minVal, int maxVal, boolean isBST) {
            this.size = size;
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.isBST = isBST;
        }
    }
    public int largestBSTSubtree(TreeNode root) {
        return postOrderTraversal(root).size;
    }

    private SubtreeInfo postOrderTraversal(TreeNode node) {
        if (node == null) {
            return new SubtreeInfo(
                0, Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        }

        SubtreeInfo leftInfo = postOrderTraversal(node.left);
        SubtreeInfo rightInfo = postOrderTraversal(node.right);

        if (leftInfo.isBST && rightInfo.isBST && leftInfo.maxVal < node.val
            && node.val < rightInfo.minVal) {
            int size = leftInfo.size + rightInfo.size + 1;
            int minVal = Math.min(leftInfo.minVal, node.val);
            int maxVal = Math.max(rightInfo.maxVal, node.val);

            return new SubtreeInfo(size, minVal, maxVal, true);
        } else {
            int size = Math.max(leftInfo.size, rightInfo.size);
            return new SubtreeInfo(
                size, Integer.MIN_VALUE, Integer.MAX_VALUE, false);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        def post_order(node: TreeNode) -> SubtreeInfo:
            if not node:
                return SubtreeInfo(0, float("inf"), float("-inf"), True)

            left_info = post_order(node.left)
            right_info = post_order(node.right)

            if (
                left_info.is_bst
                and right_info.is_bst
                and left_info.max_val < node.val < right_info.min_val
            ):
                size = left_info.size + right_info.size + 1
                min_val = min(left_info.min_val, node.val)
                max_val = max(right_info.max_val, node.val)
                return SubtreeInfo(size, min_val, max_val, True)
            else:
                size = max(left_info.size, right_info.size)
                return SubtreeInfo(size, float("-inf"), float("inf"), False)

        return post_order(root).size