Leetcode 98. Validate Binary Search Tree

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

Test Cases

Example 1:

Taken from Leetcode.com

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

Example 2:

Taken from Leetcode.com

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 [1, 104].
• -2^31 <= Node.val <= 2^31 - 1

Approach

A binary search tree is a tree where all the left children of the root have a value less than the root’s value and all the right children of the root have a value greater than the root’s value.

This is the only condition we have to check in order to solve this question.

We will be using recursion to solve this problem and we maintain a low value and a high value. The lowest value of the tree will be on the left-most end and the high value of the tree will be on the right-most end.
So we must not have any value that will be lower than the lowest value possible or any value that will be greater than the highest value possible.

Algorithm

1. Start recursion from the root node and set the lowest value as Long.MIN_VALUE and set the highest value as Long.MAX_VALUE.
   recursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
2. Inside the recursion function, if the node is null, just return true as this is the base condition.
3. Check whether the current node value is either less than the lowest value or greater than the highest value. If yes return false as this will not be a binary search tree.
4. Else continue our recursion for the left child and right child. For the left child recursion update the highest value as node.data and for the right child recursion, update the lowest value as node.data.
   recursion(root.left, low, root.val) && recursion(root.right, root.val, high).

Time and Space Complexity

We are traversing through the whole node, so the time complexity will be O(n) where n = the number of nodes.

The space complexity will be O(h) where h = height of the tree.

Code

Java Code

LeetCodeTopInterviewQuestions/11_Validate_Binary_Search_Tree.java at master ·…