From 2b5bbb98ca791a0c848febd3f02ed81469fef484 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Sat, 21 Nov 2020 14:14:50 +0000
Subject: Refactor existing bst-checker implementation

I believe the previous solution is invalid. This solution works and it should be
more time and space efficient.

Space-wise our stack grows proportionate to the depth of our tree, which for a
"balanced" BST should be log(n). Doing a BFT on a BST results in memory usage of
n because when we encounter the leaf nodes at the final level in the tree, they
will be 1/2 * n for a balanced BST.
---
 scratch/facebook/bst-checker.py | 50 +++++++++--------------------------------
 1 file changed, 10 insertions(+), 40 deletions(-)

(limited to 'scratch/facebook/bst-checker.py')

diff --git a/scratch/facebook/bst-checker.py b/scratch/facebook/bst-checker.py
index 50edeeaa1997..7ef63a95315e 100644
--- a/scratch/facebook/bst-checker.py
+++ b/scratch/facebook/bst-checker.py
@@ -6,47 +6,17 @@ class Node(object):
         self.left = left
         self.right = right
 
-    def insert_left(self, value):
-        self.left = Node(value)
-        return self.left
-
-    def insert_right(self, value):
-        self.right = Node(value)
-        return self.right
-
-    def min(self):
-        xs = deque()
-        result = float('inf')
-        xs.append(self)
-        while xs:
-            node = xs.popleft()
-            result = min(result, node.value)
-            if node.left:
-                xs.append(node.left)
-            if node.right:
-                xs.append(node.right)
-        return result
-
-    def max(self):
-        xs = deque()
-        result = float('-inf')
-        xs.append(self)
-        while xs:
-            node = xs.popleft()
-            result = max(result, node.value)
-            if node.left:
-                xs.append(node.left)
-            if node.right:
-                xs.append(node.right)
-        return result
-
     def is_bst(self):
-        result = True
-        if self.left:
-            result = result and self.left.max() < self.value
-        if self.right:
-            result = result and self.right.min() > self.value
-        return result
+        s = []
+        s.append((float('-inf'), self, float('inf')))
+        while s:
+            lo, node, hi = s.pop()
+            if lo <= node.value <= hi:
+                node.left and s.append((lo, node.left, node.value))
+                node.right and s.append((node.value, node.right, hi))
+            else:
+                return False
+        return True
 
 
 x = Node(
-- 
cgit 1.4.1