algoadvance

Leetcode 98. Validate Binary Search Tree

Problem Statement

You are given the root of a binary tree. Determine if it is a valid binary search tree (BST).

A binary search tree (BST) is a binary tree in which for each node:

Clarifying Questions

  1. Do the tree nodes have unique values?
    • Yes, typically BST nodes have unique values.
  2. What should be returned if the tree is empty?
    • An empty tree is considered a valid BST, so return true.
  3. What are the ranges of the node values?
    • Typical integer ranges: INT_MIN (-2^31) to INT_MAX (2^31 - 1).

Strategy

We can solve this problem by recursively traversing the tree while validating the BST properties. Specifically, we can employ an in-order traversal approach, where each node is visited in a sorted order. Alternatively, we can use a recursive helper function to ensure all node values fall within the valid range.

Approach:

  1. Use a helper function that checks the validity of each subtree by passing down the valid range for the node values.
  2. Initially, the complete range is passed (INT_MIN to INT_MAX).
  3. As we traverse:
    • For the left subtree, the range becomes (minValue, node.val - 1).
    • For the right subtree, the range becomes (node.val + 1, maxValue).

Code

Here’s the C++ implementation of the above strategy:

#include <climits>  // For INT_MIN and INT_MAX
#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }

private:
    bool validate(TreeNode* node, long minValue, long maxValue) {
        if (!node) return true;
        if (node->val <= minValue || node->val >= maxValue) return false;
        return validate(node->left, minValue, node->val) && 
               validate(node->right, node->val, maxValue);
    }
};

// Helper function to insert nodes into the tree (for testing purpose)
TreeNode* insertNode(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

int main() {
    Solution solution;
    TreeNode* root = new TreeNode(10);
    insertNode(root, 5);
    insertNode(root, 15);
    insertNode(root, 2);
    insertNode(root, 7);
    insertNode(root, 12);
    insertNode(root, 17);
    
    std::cout << "Is valid BST: " << solution.isValidBST(root) << std::endl;
    // Output should be: true
    
    return 0;
}

Time Complexity

The time complexity of this algorithm is (O(n)), where (n) is the number of nodes in the binary tree. Each node is visited exactly once.

Space Complexity

The space complexity is (O(h)), where (h) is the height of the tree. This space is used on the call stack due to the recursion. In the worst case (for a skewed tree), this space complexity can be (O(n)). For a balanced tree, the space complexity will be (O(\log n)).

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