diff options
| -rw-r--r-- | scratch/facebook/interview-cake/bst-checker.py | 14 |
1 files changed, 14 insertions, 0 deletions
diff --git a/scratch/facebook/interview-cake/bst-checker.py b/scratch/facebook/interview-cake/bst-checker.py new file mode 100644 index 000000000000..bbd52fa9c64c --- /dev/null +++ b/scratch/facebook/interview-cake/bst-checker.py @@ -0,0 +1,14 @@ +def is_valid(node): + """ + Return True if `node` is a valid binary search tree. + """ + s = [] + s.append((float('-inf'), node, float('inf'))) + while s: + lo, node, hi = s.pop() + if lo <= node.value <= hi: + node.lhs and s.append((lo, node.lhs, node.value)) + node.rhs and s.append((node.value, node.rhs, hi)) + else: + return False + return True |