LeetCode 101: 98 Validate Binary Search Tree

LeetCode Problem: 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/description/

Problem Description:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

Input:
    5
   / \
  1   4
     / \
    3   6
Output: false

Original Code (Recursive Approach):

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(root, low=float('-inf'), high=float('inf')):  # Validation function with initial range
            if not root:
                return True  # If the node is null, it's a valid BST
            if not (low < root.val < high):  # Check if current node's value is within the valid range
                return False

            # Recursively check left and right subtrees with updated ranges
            return validate(root.left, low, root.val) and validate(root.right, root.val, high)

        return validate(root)  # Start validation from the root

Line-by-Line Explanation and Example Execution:

1. def isValidBST(self, root: Optional[TreeNode]) -> bool:

   • Defines the main function isValidBST, which takes the root of a binary tree and returns whether it is a valid BST.

2. def validate(root, low=float('-inf'), high=float('inf')):

   • Defines a nested validation function validate that takes the current node root and the valid range (low and high).

3. if not root:

   • Checks if the current node is null. If so, returns True because an empty tree is a valid BST.

4. if not (low < root.val < high):

   • Checks if the current node’s value is within the valid range. If not, returns False.

5. return validate(root.left, low, root.val) and validate(root.right, root.val, high)

   • Recursively validates the left and right subtrees:
     • For the left subtree, the valid range is low to root.val.
     • For the right subtree, the valid range is root.val to high.
   • Only returns True if both subtrees are valid.

6. return validate(root)

   • Initiates the validation process from the root node.

Example Execution:

Assuming we have the following binary tree:

    2
   / \
  1   3

Execution steps:

1. Initial Call:

   • root = 2
   • Calls validate(2, -inf, inf).

2. Validating the Root Node:

   • The current node 2 is within the range (-inf, inf).
   • Recursively calls:
     • Left subtree: validate(1, -inf, 2)
     • Right subtree: validate(3, 2, inf)

3. Validating the Left Subtree:

   • The current node 1 is within the range (-inf, 2).
   • Recursively calls:
     • Left subtree: validate(None, -inf, 1) → Returns True
     • Right subtree: validate(None, 1, 2) → Returns True
   • Left subtree is valid, returns True.

4. Validating the Right Subtree:

   • The current node 3 is within the range (2, inf).
   • Recursively calls:
     • Left subtree: validate(None, 2, 3) → Returns True
     • Right subtree: validate(None, 3, inf) → Returns True
   • Right subtree is valid, returns True.

5. Final Result:

   • Both the left and right subtrees are valid, returns True.

Time Complexity Analysis:

• Time Complexity: O(n)
  • Where n is the number of nodes. Each node is visited once.

Space Complexity Analysis:

• Space Complexity: O(h)
  • Where h is the height of the tree. In the worst case (a skewed tree), it can go up to O(n), but on average it is O(log n).

Tips and Warnings:

1. Edge Cases:

   • Consider cases where the tree is empty or consists of a single node.

2. Understanding Recursion:

   • Make sure to understand how to set and update the valid range.

3. Properties of Binary Search Trees:

   • Familiarity with the definitions and properties of binary search trees will help in understanding the problem.

Summary

• Recursive Method: Effectively validates a binary search tree, with a time complexity of O(n) and a space complexity of O(h).
• Clear and Understandable: The code is straightforward and easy to understand, suitable for handling this type of problem.

Application Tips

1. Choose Appropriate Methods:

   • Select the method best suited to specific problem requirements to ensure efficiency and readability.

2. Handle Edge Cases:

   • Always consider edge cases in algorithm design to avoid potential errors.

3. Optimize Space Usage:

   • When handling large datasets, consider using space-efficient algorithms.

The reason we need an auxiliary function like validate is that it helps us maintain additional boundary information (low and high) during the recursion, allowing us to accurately determine whether each node satisfies the binary search tree (BST) property. Below, I’ll explain in detail why we need to use the validate function and its purpose.

1. Definition of a Binary Search Tree (BST)

A Binary Search Tree (BST) has the following properties:

• For any given node root:
  • All nodes in its left subtree must have values less than root.val.
  • All nodes in its right subtree must have values greater than root.val.

This property applies not just to the immediate left and right children but to all nodes in the left and right subtrees.

For example, consider the following binary tree:

    5
   / \
  3   7
 / \ / \
2  4 6  8

• The left subtree of the root 5 is [3, 2, 4], where all values are less than 5.
• The right subtree of the root 5 is [7, 6, 8], where all values are greater than 5.

Thus, this tree satisfies the BST properties.

2. Limitations of Directly Comparing Left and Right Nodes

If we only check the direct left and right children’s values using root.left.val < root.val < root.right.val, we can only ensure the immediate children satisfy the property, but we cannot guarantee that the entire subtree conforms to the BST properties.

Example of Incorrect BST

Consider the following incorrect BST:

    5
   / \
  1   4
     / \
    3   6

• The root node 5 has left child 1 and right child 4. The condition 1 < 5 < 4 appears to hold, but the subtree is not a valid BST.
• Node 3 in the right subtree is less than 5, violating the BST property that all nodes in the right subtree must be greater than 5.

This shows that simply comparing direct left and right children’s values is insufficient for determining whether a tree is a valid BST.

3. Why Use an Auxiliary Function validate

To correctly determine if a tree is a valid BST, we need to maintain additional constraints (lower and upper bounds) as we traverse the tree recursively. This is where the validate function comes in.

• Purpose of low and high:

  • low represents the minimum allowable value for the current node.
  • high represents the maximum allowable value for the current node.

• How validate maintains bounds:

  • When traversing the left subtree, the current node’s value becomes the upper bound (high) for all nodes in the left subtree.
  • When traversing the right subtree, the current node’s value becomes the lower bound (low) for all nodes in the right subtree.

By using the validate function with these bounds, we can ensure that every node in the tree satisfies the BST property, not just its immediate children.

4. Implementation and Explanation of the validate Function

The validate function uses the following logic:

def validate(node, low=float('-inf'), high=float('inf')):
    if not node:
        return True  # An empty node is always a valid BST

    # Check if the current node's value is within the valid range
    if not (low < node.val < high):
        return False

    # Recursively check the left and right subtrees, updating bounds
    left_is_valid = validate(node.left, low, node.val)
    right_is_valid = validate(node.right, node.val, high)

    return left_is_valid and right_is_valid

1. Initial Call:

   • validate(root, low=float('-inf'), high=float('inf')): At the root, the initial valid range is (-inf, inf).

2. Recursive Checks for Left and Right Subtrees:

   • When traversing the left subtree, node.val becomes the new upper bound (high).
   • When traversing the right subtree, node.val becomes the new lower bound (low).

3. Returning Results:

   • If node.val is not within the valid range, return False.
   • Otherwise, recursively check the left and right subtrees. The final result is True only if both subtrees are valid BSTs.

5. Why Not Directly Implement Boundary Checks in the Main Function?

Implementing the boundary checks directly in the main function can make the code more complex and less readable. Using an auxiliary function like validate helps in the following ways:

1. Keeps the Main Function Simple:

   • return validate(root) makes the main function straightforward, while the validate function handles the detailed boundary checking.

2. Easier to Maintain Boundaries:

   • The validate function can pass the low and high bounds as parameters, making it easier to update these bounds during the recursive traversal.

3. Avoids Global Variables:

   • Using parameters to pass boundary information avoids using global variables, making the function cleaner and easier to maintain.

6. Example Walkthrough Using validate

Consider the following tree:

    5
   / \
  1   7
     / \
    6   8

Initial call: validate(5, -inf, inf)

1. Check root node 5:

   • Valid range: -inf < 5 < inf
   • Left subtree range: -inf < node.val < 5
   • Right subtree range: 5 < node.val < inf

2. Check left child 1:

   • Valid range: -inf < 1 < 5
   • Left subtree range: -inf < node.val < 1
   • Right subtree range: 1 < node.val < 5

3. Check right child 7:

   • Valid range: 5 < 7 < inf
   • Left subtree range: 5 < node.val < 7
   • Right subtree range: 7 < node.val < inf

Each node’s value is within its valid range, so the tree is a valid BST.

7. Summary

• The validate function helps maintain boundaries (low and high) for each node as we traverse the tree, ensuring that every node satisfies the BST properties.
• Without validate, it would be difficult to correctly maintain these bounds and check every node’s value.
• The use of an auxiliary function makes the code cleaner, avoids global variables, and keeps the main function simple.