Interview challenge · medium · binary-tree, bst, recursion
Validate Binary Search Tree
El reto
El enunciado va en inglés, igual que en el vídeo.
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 6Idea: 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).
La solución
# Validate BST - ayotl.dev
class Node:
def __init__(self, v, l=None, r=None):
self.v, self.l, self.r = v, l, r
def is_bst(n, lo=None, hi=None):
# every node must fit its window
if not n:
return True
if lo is not None and n.v <= lo:
return False
if hi is not None and n.v >= hi:
return False
return (is_bst(n.l, lo, n.v) and
is_bst(n.r, n.v, hi))
ok = Node(2, Node(1), Node(3))
bad = Node(5, Node(1),
Node(4, Node(3), Node(6)))
print(is_bst(ok))
print(is_bst(bad))
$ python3 validate_binary_search_tree.py
True
False