Validate Binary Search Tree [Morris Traversal]

98.Validate Binary Search Tree

Tree

Binary Search Tree

Morris Traversal

Depth-First Search

Problem Statement:

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:

Input:

root = [5,1,4,null,null,3,6]

→

Output:

false

The root node's value is 5 but its right subtree contains 4 which is less than 5

Algorithm:

1. Use Morris Traversal for inorder traversal without recursion or stack
2. Track previous node to verify ascending order
3. Create and remove temporary threads to predecessor
4. Compare current with previous node during visits

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public boolean isValidBST(TreeNode root) {
    TreeNode prev = null, predecessor = null, curr = root;

    while (curr != null) {
        if (curr.left == null) {
            // Visit current node and validate BST property
            if (prev != null && prev.val >= curr.val) return false;
            prev = curr;
            
            curr = curr.right;
        } else {
            // Find the inorder predecessor
            predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) 
                predecessor = predecessor.right;
            
            if (predecessor.right == null) {
                // Create thread to current node
                predecessor.right = curr;
                curr = curr.left;
            } else {
                // Remove thread and visit current node
                predecessor.right = null;
                if (prev != null && prev.val >= curr.val) return false;
                prev = curr;
                curr = curr.right;
            }
        }
    }

    return true;
}

Python Solution:

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    prev = curr = predecessor = None
    curr = root
    
    while curr:
        if not curr.left:
            # Visit current node and validate BST property
            if prev and prev.val >= curr.val:
                return False
            prev = curr
            curr = curr.right
        else:
            # Find the inorder predecessor
            predecessor = curr.left
            while predecessor.right and predecessor.right != curr:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # Create thread to current node
                predecessor.right = curr
                curr = curr.left
            else:
                # Remove thread and visit current node
                predecessor.right = None
                if prev and prev.val >= curr.val:
                    return False
                prev = curr
                curr = curr.right
                
    return True

C++ Solution:

bool isValidBST(TreeNode* root) {
    TreeNode *prev = nullptr, *predecessor = nullptr, *curr = root;
    
    while (curr) {
        if (!curr->left) {
            // Visit current node and validate BST property
            if (prev && prev->val >= curr->val) return false;
            prev = curr;
            curr = curr->right;
        } else {
            // Find the inorder predecessor
            predecessor = curr->left;
            while (predecessor->right && predecessor->right != curr)
                predecessor = predecessor->right;
            
            if (!predecessor->right) {
                // Create thread to current node
                predecessor->right = curr;
                curr = curr->left;
            } else {
                // Remove thread and visit current node
                predecessor->right = nullptr;
                if (prev && prev->val >= curr->val) return false;
                prev = curr;
                curr = curr->right;
            }
        }
    }
    
    return true;
}