A product catalogue is indexed by price in a binary tree, and it's only fast if the tree is a valid binary search tree. Write a function that returns whether it is: for every node, all values in its left subtree are strictly smaller, and all values in its right subtree are strictly larger. An empty tree counts as valid.
9 is in 8's left subtree, so it would need to be smaller than 8.
In the second example, 9 sits in the left subtree of 8 (as 3's right child), but 9 isn't smaller than 8. In the third, equal values aren't allowed.
Write is_search_tree(root) in Python or isSearchTree(root) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
The tempting wrong answer
Checking left.val < node.val < right.val at every node passes the second example, but that tree isn't valid. The rule is about whole subtrees, not just children.
Step 2
Every node has an allowed range
The root can be anything. Its left child must be below the root's value; its right child must be above it. Go one level further and the ranges get tighter: 3's right child must be above 3 and below 8.
Going left lowers the upper limit; going right raises the lower limit.
Step 3
Pass the range down
Write valid(node, low, high): the node's value must be strictly between low and high. For the left child, call valid(node.left, low, node.val); for the right, valid(node.right, node.val, high). Start with no limits (-infinity, +infinity, or None).
Step 4
Another way: in-order traversal
An in-order traversal of a valid BST produces values in strictly increasing order. Walking the tree in order and checking each value against the previous one also works, in the same O(n).
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Recursively check that each node's value lies strictly between the lowest and highest values allowed by its ancestors, tightening the upper bound when going left and the lower bound when going right. An empty subtree is valid.
python
1def is_search_tree(root):
2 def valid(node, low, high):
↑low and high: the allowed range
3 if node is None:
4 return True
5 if (low is not None and node.val <= low) or (high is not None and node.val >= high):
↑outside the range: not a BST
6 return False
7 return valid(node.left, low, node.val) and valid(node.right, node.val, high)