Jason's Notebook

Validate Binary Search Tree

2 min read

Medium

Description

Validate Binary Search Tree - Leetcode

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 subtree1 of a node contains only nodes with keys strictly less than the node’s key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Examples

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node’s value is 5 but its right child’s value is 4.

Constraints

  • The number of nodes in the tree is in the range

Code

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {return true;}
        bool leftIsBST = isLessThan(root->left, root->val) && isValidBST(root->left);
        bool rightIsBST = isGreaterThan(root->right, root->val) && isValidBST(root->right);
        return leftIsBST && rightIsBST;
    }
 
    bool isLessThan(TreeNode* node, int val){
        if (node == nullptr) {return true;}
        return node->val < val && isLessThan(node->left, val) && isLessThan(node->right, val);
    }
 
    bool isGreaterThan(TreeNode* node, int val){
        if (node == nullptr) {return true;}
        return node->val > val && isGreaterThan(node->left, val) && isGreaterThan(node->right, val);
    }
};

Approach

  1. check if the tree exist by checking root
  2. check if the left subtree is a valid Binary Search Tree through isLessThan() helper function
    • Takes 2 parameter:
      • node: The root of the subtree
      • val: value of the root overall tree
    1. Check if the subtree exist by checking subtree root
    2. Continue to check the left and right subtree recursively
    3. return the whether it is valid

IMPORTANT

right subtree on the left should still be less than the overall tree’s root

  1. check if the right subtree is a valid Binary Search Tree through isGreaterThan() helper function Takes 2 parameter: - node: The root of the subtree - val: value of the root overall tree
    1. Check if the subtree exist by checking subtree root
    2. Continue to check the left and right subtree recursively
    3. return the whether it is valid

IMPORTANT

Left subtree on the right should still be greater than the overall tree’s root

Footnotes

  1. A subtree of treeName is a tree consisting of a node in treeName and all of its descendants. ↩

Graph View