Solution: Validate Binary Search Tree

Statement#

Given the root of a binary tree, check whether it is a valid binary search tree (BST).

A binary tree is a valid BST if for every node:

• The value of the node is greater than or equal to the value of its left node.

• The value of the node is less than or equal to the value of its right node.

• Both the left and right subtrees are valid BSTs.

Constraints:

• $-10^{4} \leq$ Node.data $\leq 10^{4}$

• The tree contains nodes in the range $[1, 500]$.

Solution#

For this solution, we will recursively perform the inorder (left subtree, root, right subtree) traversal on the binary tree. We will be using inorder traversal to get elements in sorted order. We will also use a prev variable to hold the value of the previous node visited during the inorder traversal.

We initialize the prev variable with negative infinity. Then, we perform the inorder traversal on the tree and check whether the current node’s value is less than the prev value. If it is, return FALSE since it is not a valid BST. If not, update the value of prev with the current node’s value, and continue the traversal. If all nodes have been traversed and no node’s value was less than the prev value, it means that the tree is a valid BST. Therefore, we return TRUE.

Let’s look at an example below:

Let’s implement the algorithm as discussed above:

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ represents the number of nodes in the binary tree.

Space complexity#

The space complexity of this solution is $O(n)$. This is because our recursive algorithm uses space on the call stack.