algoadvance

Leetcode 98. Validate Binary Search Tree

Problem Statement:

You are given a binary tree and need to determine if it is a valid Binary Search Tree (BST).

A valid BST is defined as follows:

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

Clarifying Questions:

  1. What should be the structure of the binary tree node?
    • Typically, a binary tree node contains an integer value, and references to its left and right children.
  2. What should be returned as the result?
    • Return true if the binary tree is a valid BST; otherwise, return false.
  3. Can the tree be empty?
    • Yes, if the tree is empty, it is considered a valid BST.

Strategy:

  1. Recursive In-Place Validation:
    • Use a helper function that validates the tree by ensuring that all nodes’ values stay within the allowable range defined by their parent nodes.
    • The allowable range ensures that for any node, left < node < right.
  2. Initial Range:
    • For the root node, the range is set to negative infinity to positive infinity.
  3. Traversal:
    • Traverse the tree starting from the root.
    • For the left subtree, update the maximum acceptable value.
    • For the right subtree, update the minimum acceptable value.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

    private boolean validate(TreeNode node, long min, long max) {
        // An empty tree is a valid BST
        if (node == null) {
            return true;
        }
        
        // The current node's value must be between min and max
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        // Recursively validate the left subtree and right subtree
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

Time Complexity:

Each node is checked once to ensure it falls within the valid range, and the recursion stack ensures we process the entire tree efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI