Validate BST

Validate BST

Validate BST aims to determine whether a given binary tree is a valid binary search tree (BST).

A BST is a binary tree where each node's value is greater than all values in its left subtree and less than all values in its right subtree.

Here's my solution:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        """
        Initialize a TreeNode with a value and optional left and right children.

        Args:
            value (int, optional): The value of the node. Defaults to 0.
            left (TreeNode, optional): The left child of the node. Defaults to None.
            right (TreeNode, optional): The right child of the node. Defaults to None.
        """
        self.value = value
        self.left = left
        self.right = right

# O(n) time coz you have to traverse every single node | 
# O(d) space coz we will at most have d calls(frames) on the callstack being used up
def validate_bst(tree):
    """
    Validate whether a binary tree is a valid binary search tree (BST).

    Args:
        tree (TreeNode): The root of the binary tree to be validated.

    Returns:
        bool: True if the tree is a valid BST, False otherwise.
    """
    return validate_bst_helper(tree, float("-inf"), float("inf"))


def validate_bst_helper(tree, min_value, max_value):
    """
    Helper function to recursively validate whether a binary tree is a valid BST within a given range.

    Args:
        tree (TreeNode): The current node being validated.
        min_value (int): The minimum allowable value for nodes in the subtree.
        max_value (int): The maximum allowable value for nodes in the subtree.

    Returns:
        bool: True if the subtree rooted at the current node is a valid BST, False otherwise.
    """
    # Base case: If the current node is None, return True
    if tree is None:
        return True
    
    # Check if the current node's value violates the BST property
    if tree.value < min_value or tree.value >= max_value:
        return False
    
    # Recursively validate the left subtree and right subtree
    # Update the range constraints accordingly
    left_is_valid = validate_bst_helper(tree.left, min_value, tree.value)
    right_is_valid = validate_bst_helper(tree.right, tree.value, max_value)
    
    # Return True only if both left and right subtrees are valid BSTs
    return left_is_valid and right_is_valid


# Example usage:
# Construct a binary tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

# Validate whether the tree is a valid BST
is_valid_bst = validate_bst(root)
print("Is the tree a valid BST?", is_valid_bst)

Let's break down the solution:

Function validate_bst(tree)

This is the entry point of the solution. It calls the helper function validate_bst_helper() with the root of the binary tree (tree) and initial minimum and maximum values set to negative infinity and positive infinity, respectively.

Function validate_bst_helper(tree, min_value, max_value)

This helper function recursively validates whether the binary tree (tree) satisfies the properties of a BST within the given range (min_value to max_value).

It returns True if the tree is a valid BST within the specified range, and False otherwise.

Base Case

If the current node is None, it means the subtree is empty, so it returns True.

If the current node's value is less than the min_value or greater than or equal to the max_value, it violates the BST property, so it returns False.

Recursive Step

It recursively validates the left subtree and right subtree with updated ranges. For the left subtree, the maximum value is updated to the current node's value because all nodes in the left subtree must be less than the current node.

And for the right subtree, the minimum value is updated to the current node's value since all nodes in the right subtree must be greater than the current node.

It returns the logical AND of the validity of the left subtree and the validity of the right subtree. This ensures that both subtrees are valid BSTs for the overall tree to be a valid BST.

Time Complexity

Traversal: The solution performs a depth-first traversal of the entire binary tree.

Validation: At each node of the tree, the validate_bst_helper() function recursively validates whether the subtree rooted at that node is a valid BST.

This validation involves visiting each node once and performing constant-time operations (comparisons and recursive calls).

Since every node in the binary tree is visited exactly once, the time complexity of the solution is O(n), where n is the number of nodes in the binary tree.

Space Complexity

Recursive Call Stack: The space complexity of the recursive call stack depends on the maximum depth of recursion, which is equal to the height of the binary tree.

In the worst-case scenario, when the tree is completely unbalanced (i.e., a skewed tree), the height of the tree is n (where n is the number of nodes). Therefore, the space complexity due to the call stack is O(n).

Auxiliary Space: Besides the call stack, the solution does not use any additional space that scales with the input size. The space required for maintaining variables and parameters during the recursive calls is constant.

Considering both the recursive call stack and auxiliary space, the space complexity of the solution is O(n).

Unit Tests

The following unit tests cover various scenarios:

•     Testing a valid BST
•     Testing an invalid BST
•     Testing an empty tree
•     Testing a single-node tree
•     Testing a BST with duplicate values
•     Testing a BST with negative values

In each of the test cases, the validate_bst() function returns the expected result for a given input tree. These tests help ensure the robustness of the solution by validating its behavior under different conditions.

import unittest


class TestValidateBST(unittest.TestCase):
    def test_valid_bst(self):
        # Construct a valid binary search tree
        root = TreeNode(2)
        root.left = TreeNode(1)
        root.right = TreeNode(3)
        
        # Validate the BST
        self.assertTrue(validate_bst(root))
    
    def test_invalid_bst(self):
        # Construct an invalid binary search tree
        root = TreeNode(5)
        root.left = TreeNode(1)
        root.right = TreeNode(4)
        root.right.left = TreeNode(3)
        root.right.right = TreeNode(6)
        
        # Validate the BST
        self.assertFalse(validate_bst(root))
    
    def test_empty_tree(self):
        # An empty tree is considered a valid BST
        self.assertTrue(validate_bst(None))
    
    def test_single_node(self):
        # A single node is considered a valid BST
        root = TreeNode(5)
        self.assertTrue(validate_bst(root))
    
    def test_duplicate_values(self):
        # Construct a binary search tree with duplicate values
        root = TreeNode(2)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        
        # Validate the BST
        self.assertFalse(validate_bst(root))
    
    def test_negative_values(self):
        # Construct a binary search tree with negative values
        root = TreeNode(-2)
        root.left = TreeNode(-3)
        root.right = TreeNode(-1)
        
        # Validate the BST
        self.assertTrue(validate_bst(root))


if __name__ == '__main__':
    unittest.main()