Daily bit(e) of C++ | Validating a BST
Daily bit(e) of C++ #93, Common interview problem: Validating a BST
Today we will look at a common C++ interview problem: Validating a BST
Given a binary tree, validate that it is a binary search tree.
for each node, all nodes in the left sub-tree have strictly lower values
for each node, all nodes in the right sub-tree have strictly higher values
In the above example, the tree is not a valid binary search tree since the right sub-tree condition is violated between nodes 8 and 7.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/WKe14x93v.
Solution
If we are checking a particular node in a binary search tree, going to the left subtree sets an upper bound on all the values in the subtree and going to the right subtree sets a lower bound on all the values in the subtree.
We need to keep track of these bounds as we explore the tree using pre-order traversal. The tree is a valid binary search tree if we find no violation and isn't valid if we do.
