BST Insert and Search

The Idea

Searching a BST is one comparison per level: smaller means go left, larger means go right, and the other side is discarded outright. Insertion follows that identical path and stops at the first empty slot. Both cost O(h), the height of the tree.

Real-World Example

A recycling line's weight gates. Each item meets a gate that asks only "heavier or lighter than this?" and gets flicked one way, gate after gate, until it drops into a free bin. Looking up a known weight later walks exactly the same gates.

The Code

class Node:
    def __init__(self, v): self.val, self.left, self.right = v, None, None
def insert(root, v):
    if root is None: return Node(v)        # empty slot: the value lands here
    if v < root.val: root.left = insert(root.left, v)
    else: root.right = insert(root.right, v)
    return root
def search(root, v):
    while root and root.val != v:          # each step drops one whole side
        root = root.left if v < root.val else root.right
    return root is not None

root = Node(50)
for v in [30, 70, 20, 40]: insert(root, v)
print(search(root, 40), search(root, 45))  # True False

class Node:
  def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

root = Node(50, Node(30, Node(20), Node(40)), Node(70))
node, path = root, []
while node:
  path.append(node.val)
  if node.val == 40: break
  node = ___
print(path)   # should print [50, 30, 40]