# Title: Binary search tree
# Heading: Python Program to Implement a Binary Search Tree
# Level: intermediate
# Tags: binary search tree, bst, insert, search, tree
# Time: O(h)
# Space: O(n)
# About: Builds a binary search tree, where smaller values go left and larger ones right, then searches it and lists its values in sorted order.

class Node:
    """A value with a left and a right subtree."""

    def __init__(self, value):
        self.value = value
        self.left = None   # smaller values
        self.right = None  # larger or equal values


def insert(node, value):
    """Add value to the tree; return the tree's root."""
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node


def search(node, value):
    """True if value is in the tree under node."""
    while node:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def in_order(node, values):
    """Add the tree's values to values, smallest first."""
    if node:
        in_order(node.left, values)
        values.append(node.value)
        in_order(node.right, values)
    return values


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)
print("Sorted:", in_order(root, []))
print("Has 60:", search(root, 60))
print("Has 65:", search(root, 65))