"Binary trees and binary search trees"
# MCS 275 Spring 2022 Lectures 18-21


class Node:
    "Node in a binary tree"

    def __init__(self, key=None, left=None, right=None, parent=None):
        """Create a new node with left child `left`,
        right child `right`, and key `key`"""
        self.left = left
        self.right = right
        self.parent = parent
        self.key = key

    def preorder(self):
        "Return a list of keys in preorder"
        L = []
        L.append(self.key)
        if self.left:
            L.extend(self.left.preorder())
        if self.right:
            L.extend(self.right.preorder())
        return L

    def postorder(self):
        "Return a list of node keys in preorder"
        L = []
        if self.left:
            L.extend(self.left.postorder())
        if self.right:
            L.extend(self.right.postorder())
        L.append(self.key)
        return L

    def inorder(self):
        "Return a list of node keys in preorder"
        L = []
        if self.left:
            L.extend(self.left.inorder())
        L.append(self.key)
        if self.right:
            L.extend(self.right.inorder())
        return L

    def __str__(self):
        "Human-readable string representation"
        return "[{}]".format(self.key)

    def __repr__(self):
        "Unambiguous string representation"
        return str(self)

    def set_left(self, other):
        "Make node `other` the left child of this one"
        self.left = other
        other.parent = self

    def set_right(self, other):
        "Make node `other` the right child of this one"
        self.right = other
        other.parent = self


class BST(Node):
    "Binary search tree class (with recursive insert, search)"

    def search(self, k):
        """
        Find a node in this tree with key `k` and return it;
        return None if no such node exists.
        """
        if self.key == None:
            return None
        if k == self.key:
            return self
        elif k < self.key:
            # the node with key `k` must be in the left subtree
            if self.left == None:
                return None
            else:
                return self.left.search(k)
        elif self.key < k:
            # the node with key `k` must be in the right subtree
            if self.right == None:
                return None
            else:
                return self.right.search(k)

    def __contains__(self, k):
        """
        Return boolean indicating whether the tree contains
        a node with key k
        """
        return self.search(k) != None

    def insert(self, k):
        """
        Find a suitable place to add a new node to this BST
        with key `k`, and add it.
        """
        if self.key == None:
            # Empty tree, so just add k as the key of *this* node
            self.key = k
            return
        if k <= self.key:
            if self.left == None:
                # k belongs to the left, and the left is empty.
                self.set_left(BST(key=k))
            else:
                # Have the left subtree handle it!
                self.left.insert(k)
        else:
            if self.right == None:
                self.set_right(BST(key=k))
            else:
                self.right.insert(k)


# x in L
#  becomes
# L.__contains__(x)