Problem 🤔

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.

Example 1

Input: root = [2,1,3]

Output: true

Example 2

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.

Real World Applications 🌎

In the case that you need to actually build a binary tree in production a utility like this would come in handy to confirm you’re doing it right. Since most of us aren’t building BSTs on the daily, I like this problem because it requires understanding the recursive nature of this data structure.

The Finer Details 🔎

Checking a node against its parent is not enough! Remember, the definition of a binary search tree is that every node in the left subtree is smaller and every node in the right sub tree is larger. Now, this is true for every node in the tree! So we need to confirm that the nodes in the subtrees maintain the size constraints for all nodes above! Basically, we need to keep track of an upper and lower bound for each level.

So, what is the most inuitive way to confirm this? Recursion, yes, but which?

Well, it would be be great to confirm that the left and right sub trees are valid. With two valid sub trees from the root we’d be done! So let’s go ahead and implement that with a divide and conquer approach!

Recursive Solution 💡

Takeaways 🎉🥳

Remember, a binary search trees qualities need to be upheld for every node in the tree! So checking the parent in this instance is not enough, we need to confirm this against the ancestors as well!

Resources 📚 💻

Leetcode