Interview challenge · medium · binary-tree, bst, recursion

Validate Binary Search Tree

The challenge

Given the root of a binary tree, decide whether it is a valid binary search tree: for every node, all the values in its left subtree are smaller than the node and all the values in its right subtree are bigger.

Example

  2
 / \          ->  true
1   3

  5
 / \
1   4         ->  false  (4 is in the right subtree of 5)
   / \
  3   6

Idea: checking each node against its children is not enough: the 4 above is bigger than its own children and still wrong. Instead, pass every node the window it must fit in. Going left lowers the top of the window to the node's value; going right raises the bottom. Time O(n), stack O(height).

The solution

1# Validate BST - ayotl.dev
2class Node:
3    def __init__(self, v, l=None, r=None):
4        self.v, self.l, self.r = v, l, r
5
6
7def is_bst(n, lo=None, hi=None):
8    # every node must fit its window
9    if not n:
10        return True
11    if lo is not None and n.v <= lo:
12        return False
13    if hi is not None and n.v >= hi:
14        return False
15    return (is_bst(n.l, lo, n.v) and
16            is_bst(n.r, n.v, hi))
17
18
19ok = Node(2, Node(1), Node(3))
20bad = Node(5, Node(1),
21           Node(4, Node(3), Node(6)))
22print(is_bst(ok))
23print(is_bst(bad))

$ python3 validate_binary_search_tree.py

True

False

The video

Watch on YouTube →