Prerequisites :- Binary Search Trees, BT traversals.
Problem :- Check if the given binary tree is a valid Binary Search Tree (BST).
A valid BST adheres to the following criteria:
- The left subtree of a node comprises only nodes with keys less than the node’s key.
- The right subtree of a node comprises only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be valid Binary Search Trees.
Solution Approach :-
To check if a binary tree is a valid BST, we can use a recursive approach. The key observation is that for each node, its value must be within a specific range. The left subtree of a node must have values less than the node’s value, and the right subtree must have values greater than the node’s value. These ranges change as we traverse down the tree.
Please take a deeper look at the solution to understand this.
Time complexity :- O(N), because in the worst case, the algorithm visits all the nodes in the given BST.
Space complexity :- O(1), as no extra space is needed.