98. Validate Binary Search Tree

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.

Approach 1:

This approach utilizes an in-order traversal to check whether the values of nodes are in increasing order. The key idea is to check that the current node's value is greater than the previous node's value during traversal.

Code Implementation (Java)

class Solution {
    boolean res = true;
    Integer prev = null;

    public void traversal(TreeNode root) {
        if (root == null)
            return;
        traversal(root.left);

        if (prev != null && root.val <= prev) {
            res = false;
            return;
        }
        prev = root.val;
        traversal(root.right);
    }

    public boolean isValidBST(TreeNode root) {
        traversal(root);
        return res;
    }
}
        

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree. Space Complexity: O(n), due to the recursion stack in the worst case.

The problem Validate Binary Search Tree asks to verify if a given binary tree is a valid Binary Search Tree (BST). A binary search tree is defined as a binary tree in which each node follows the constraints:

• 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.

Problem Statement

Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST must satisfy the aforementioned constraints at every node in the tree.

Approach to Solve the Problem

To validate a binary search tree, we need to ensure that each node in the tree follows the BST property. This can be done using a recursive approach. For each node, we check whether its value lies within a valid range, and we recursively check its left and right subtrees to ensure they also satisfy the BST properties.

The main idea is to traverse the tree in a depth-first manner and keep track of the valid range for each node. The range for a node is determined by the values of its parent and its ancestors. At each node, we ensure that the node's value is within the valid range, and recursively apply the same checks for its left and right children.

Steps for Validating the Binary Search Tree

1. Perform a depth-first traversal of the tree.
2. For each node, ensure its value is within the valid range defined by its parent and ancestors.
3. For the left child, the value must be less than the current node's value, and for the right child, the value must be greater.
4. Recursively validate the left and right subtrees.

Here is the Java implementation of the solution:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean helper(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return helper(node.left, lower, node.val) && helper(node.right, node.val, upper);
    }
}
        

Example

Consider the following binary tree:

            Tree Structure:
                2
               / \
              1   3
        

In this case, the tree is a valid BST because:

• The left subtree of 2 contains 1, which is less than 2.
• The right subtree of 2 contains 3, which is greater than 2.
• Both subtrees follow the BST properties.

The output for this example is true.

Now, consider this binary tree:

            Tree Structure:
                5
               / \
              1   4
                 / \
                3   6
        

In this case, the tree is not a valid BST because:

• The left subtree of 4 contains 3, which is less than 4, but the right subtree contains 6, which is greater than 4.
• The value 3 violates the BST property for the node 4.

The output for this example is false.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the binary tree. We visit each node exactly once during the depth-first traversal.

Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack used for depth-first traversal. In the worst case, the tree can be skewed, and the height could be O(n), resulting in O(n) space complexity.

Applications

• Verifying the structure of a binary search tree is important in problems involving binary tree-based algorithms, such as searching, inserting, and deleting elements.
• In some applications, you may need to ensure that a given tree is a valid BST before performing operations like searching for a particular value or calculating the tree's height.
• This problem is often used in interviews to assess a candidate's understanding of recursion and tree properties.

Conclusion

The Validate Binary Search Tree problem is a fundamental problem that tests a candidate's understanding of tree traversal and binary search tree properties. By using a recursive approach, we can efficiently validate whether a given binary tree satisfies the BST conditions. This problem reinforces key concepts in recursion, depth-first traversal, and tree validation, which are crucial for solving more complex problems involving trees and graphs.

Overall, validating a binary search tree is an essential skill in both technical interviews and real-world applications involving tree-based data structures.