Validate a binary search tree

Medium TimeO(n) SpaceO(h)

A binary search tree requires every value in a node's left subtree to be smaller than it and every value on the right to be larger — for every node, not merely for its immediate children, so a value can satisfy its parent and still break an ancestor higher up. Given a binary tree, return true when it qualifies. Values are distinct, an equal value is not valid on either side, and an empty tree is a valid one.

Examples

Example 1

Input
node = buildTree()low = nullhigh = null
Output
true
1, 2, 3 all below 4 and 6, 7, 9 all above it, and the same holds at every node.

Example 2

Input
node = { val: 4, left: { val: 2, left: null, right: { val: 5, left: null, right: null } }, right: null }low = nullhigh = null
Output
false
5 satisfies its parent 2 by being larger, but it sits in the left subtree of 4.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function isValidBST(node, low, high) {
  if (node === null) return true;
  if (low !== null && node.val <= low) return false;
  if (high !== null && node.val >= high) return false;
  if (!isValidBST(node.left, low, node.val)) return false;
  return isValidBST(node.right, node.val, high);
}
isValidBST(buildTree(), null, null);
Done

The first 8 calls, of 16. This one does not fit on a page.

Step through isValidBST(buildTree(), null, null) call by call

More like this

All binary trees examples (9) →