Is this really a search tree

A binary search tree has one rule: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. Say whether a given tree obeys it.

Worked example, and the trap#

      5
     / \
    1   4
       / \
      3   6

Check each node against its own children and everything looks fine: 1 is less than 5, 4 is more than 5, 3 is less than 4, 6 is more than 4.

But the tree is not a search tree. The 3 sits in the right subtree of the 5, and 3 is less than 5. Searching for 3 from the root would go right and never find it.

That is the whole difficulty of this problem. Checking a node against its children is not enough: a node must be within the range that every ancestor allows.

The idea#

Carry the allowed range down as you recurse. The root may be anything. Going left from a node of value v tightens the upper bound to v; going right tightens the lower bound to v.

ok(node, low, high):
    if node is nothing:            return true
    if not (low < node.val < high): return false
    return ok(node.left,  low, node.val)
       and ok(node.right, node.val, high)

In the example, the 3 arrives with low = 5 from having gone right at the root, and fails immediately.

The other way#

An inorder walk of a search tree produces its values in increasing order. So walk inorder and check each value is larger than the one before. It is the same check wearing different clothes, and it is worth writing both, because the inorder view is what makes the kth smallest problem easy.

Constraints#

• 0 <= number of nodes <= 100000
• Values are distinct

About the input#

The tree is written level by level with null for a missing child, the count first.