<jupyter_start><jupyter_text>Binary Search Trees<jupyter_code>class Node:
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right
   
    def __bool__(self):
        return not (
            self.item is None
            and self.left is None
            and self.right is None
        )

    def __str__(self):
        return str(self.item)
    
    def __repr__(self):
        return f"Node({self.item}, left={self.left}, right={self.right})"

class BST:
    def __init__(self, items):
        self.root = None
        for item in items:
            self.push(item)
            
    def __contains__(self, item):
        if self.root is None:
            return False
        return self._find(item, self.root)
    
    def _find(self, item, node):
        if item == node.item:
            return True
        elif item > node.item and node.right:
            return self._find(item, node.right)
        elif item < node.item and node.left:
            return self._find(item, node.left)
        else:
            return False
    
    def push(self, item):
        if self.root is None:
            self.root = Node(item)
        else:
            self._insert_recursively(item, self.root)

    def _insert_recursively(self, item, node):
        if item < node.item:
            if node.left is None:
                node.left = Node(item)
            else:
                self._insert_recursively(item, node.left)
        elif item > node.item:
            if node.right is None:
                node.right = Node(item)
            else:
                self._insert_recursively(item, node.right)
        else:
            raise ValueError(f"cannot push value {item}, already exists")

xtree = BST([1,3,2,7,6,8,4,5])
for i in range(10):
    if i in xtree:
        print(f"{i} in xtree")
    else:
        print(f"{i} not in xtree")
def nonrecursive_find(tree, item):
    node = tree.root
    
    i = 0
    while not (node.left is None and node.right is None):
        print(f"iteration {i} on Node({node})")
        if node.item == item:
            print(f"found on {node}!")
            break
        elif item < node.item:
            if node.left:
                print(f"item < {node}, moving onto Node({node.left})")
                node = node.left
            else:
                print(f"item < {node}, but node.left=None")
                break
        elif item > node.item and node.right:
            if node.right:
                print(f"item > {node},moving onto Node({node.right})")
                node = node.right
            else:
                print(f"item > {node}, but node.right=None")
                break
        else:
            print(f"{i}: All cases failed.")
            break
        i += 1

    return node.item == item
nonrecursive_find(xtree, 0)
def nonrecursive_find(tree, item):
    node = tree.root
    while not (node.left is None and node.right is None):
        if node.item == item:
            return True
        elif item < node.item and node.left:
                node = node.left
        elif item > node.item and node.right:
                node = node.right
        else:
            break
    
    return item == node.item
for i in range(10):
    if nonrecursive_find(xtree, i):
        print(f"{i} in xtree")
    else:
        print(f"{i} not in xtree")<jupyter_output>0 not in xtree
1 in xtree
2 in xtree
3 in xtree
4 in xtree
5 in xtree
6 in xtree
7 in xtree
8 in xtree
9 not in xtree
{'fraction_non_alphanumeric': 0.10193072118114707, 'fraction_numerical': 0.007098239636570131, 'mean_word_length': 1.6, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '611824', 'license': 'MIT', 'n_tokens_mistral': 1110, 'n_tokens_neox': 1078, 'n_words': 319, 'path': 'data-structs/binary_search_tree.ipynb', 'repo_name': 'naondo88/datastruct-n-algos', 'size': '3522'}