Trees and Binary Search Trees

A binary search tree keeps values ordered by shape so search, insert, and delete each cost O(h) where h is the tree’s height.

Vocabulary

• Node: container holding one value plus links to children. Edge: a link. Parent links down to child.
• Root: single top node, no parent. Every tree has exactly one.
• Leaf: node with no children. Subtree: a node plus everything below it.
• Depth of a node: edges from root down to it (root = 0). Height of a tree: edges on the longest root-to-leaf path (root only = 0).
• No loops; each node except the root has exactly one parent.

Binary tree and BST rule

• Binary tree: every node has at most two children, named left child and right child.
• Binary search tree (BST): binary tree where for every node, all values in the left subtree are less, all in the right subtree are greater.
• Rule holds at every node, not just the root, and is about whole subtrees, not just immediate children.
• Lets you discard half the tree each step, like binary search built into the shape.

Core operations

• Search: walk from root; go left if smaller, right if larger; stop on match or on None (not found).
• Insert: same walk; the first empty (None) spot is where the value lands. One new edge; nothing else moves. Ignore duplicates.
• In-order traversal: left subtree, then node, then right subtree. Visits values smallest to largest (sorted for free).
• Delete the found node, three cases:
  • No children (leaf): remove it, return None.
  • One child: return that child to the parent.
  • Two children: copy in the in-order successor (smallest value in the right subtree), then delete that successor from the right subtree (it has at most one child).

Recursion rules

• Every recursive tree function checks if node is None first (base case).
• Reassign the link on insert/delete: node.left = insert(node.left, value), else new nodes never attach.
• TreeNode holds value, left, right; None means no node.

Cost by shape

Everything walking the tree is O(h); balanced makes h ≈ log2(n), degenerate makes h ≈ n. Space is recursion depth, O(h).

• In-order is always O(n): it must touch every node. The others ride on height alone.
• Balanced height ≈ log2(n): a million nodes is ~20 levels.
• A plain BST does not self-balance. Inserting sorted data makes a straight line, height n-1, search O(n). AVL and red-black trees rebalance automatically.

Pitfalls

• Do not assume O(log n); it is O(h), and only balanced trees give h ≈ log n.
• Depth (root to a node) is not height (longest root-to-leaf for the tree).
• Missing the None base case raises AttributeError or recurses forever.
• Checking only direct children does not verify a BST; the property spans whole subtrees.