Validate Binary Search Tree - Leetcode Solution

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 = [2,1,3]

Output: true

Explanation: The binary tree is:

2

/
1 3

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.

Solution:

One simple approach to solve this problem is to recursively traverse through the given binary tree. While traversing, we can keep track of the smallest and largest values seen so far for each node. We can then check if the current node's value is within this range of the smallest and largest values seen so far. If it is not, we can immediately return false since the tree is not valid.

Algorithm:

• Initialize a variable prev to NULL.

• Define the isValidBSTUtil function to perform the following steps.

• If root equals to NULL, return true.

• Traverse the left subtree by calling the isValidBSTUtil function with root's left child as input argument. Store its result in a variable called left.

• If prev is not NULL and root's value is less than or equal to prev's value, return false.

• Set prev to root.

• Traverse the right subtree by calling the isValidBSTUtil function with root's right child as input argument. Store its result in a variable called right.

• Return true if both left and right are true, else false.

• Call the isValidBSTUtil function with root as input argument and return its result.

Pseudo Code:

bool isValidBSTUtil(Node* root, Node* prev) { if (root == NULL) return true;

if (!isValidBSTUtil(root->left, prev))
    return false;
    
if (prev != NULL && root->data <= prev->data)
    return false;
    
prev = root;

return isValidBSTUtil(root->right, prev);

}

bool isValidBST(Node* root) { Node* prev = NULL; return isValidBSTUtil(root, prev); }

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we need to traverse through each node of the binary tree exactly once.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the binary tree. This is because we need to keep track of the previous node as we traverse through the binary tree. The maximum possible height of a binary tree is n (number of nodes), so the space complexity is O(n) in the worst case.

Conclusion:

In this problem, we have discussed how to validate a binary search tree using a recursive approach. This solution has a time complexity of O(n) and a space complexity of O(h).

1