Solution: Validate Binary Search Tree
Let's solve the Validate Binary Search Tree problem using the Tree Depth-First Search pattern.
We'll cover the following
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 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 are valid BSTs.
Constraints:
-
Node.Data
-
The tree contains nodes in the range .
Solution
To validate a binary tree as a binary search tree (BST), use an in-order traversal to visit nodes in ascending order. During the traversal, keep track of the previously visited node’s value. Each current node’s value should be greater than this previous value because, in a BST, the left subtree of a node contains values less than the node’s value, and the right subtree contains values greater. Therefore, as you traverse the tree in-order, the sequence of node values should be strictly increasing. If, at any point, a node’s value is not greater than the previous node’s value, the tree is not a BST. This approach ensures that the tree maintains the properties of a BST by verifying that values are visited in strictly increasing order.
To implement the above algorithm, we initialize a 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:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.