Trees and Binary Search Trees

A tree is a hierarchical structure with a root node and children. A binary tree has at most two children per node. A Binary Search Tree (BST) adds ordering: left child < parent < right child.

Why It Matters

Trees model file systems, HTML/DOM, database indexes (B-trees), syntax trees in compilers, and organizational hierarchies. BSTs give O(log n) search, insert, and delete when balanced.

Terminology

Term	Meaning
Root	Top node (no parent)
Leaf	Node with no children
Height	Longest path from root to leaf
Depth	Distance from root to a node
Balanced	Height is O(log n)

BST Property

For every node: all values in the left subtree are smaller, all values in the right subtree are larger.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Operations

Operation	Average (balanced)	Worst (degenerate)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Inorder traversal	O(n)	O(n)

Code Example

class TreeNode:
    __slots__ = ('val', 'left', 'right')
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class BST:
    def __init__(self):
        self.root = None
 
    def insert(self, val):
        self.root = self._insert(self.root, val)
 
    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node
 
    def search(self, val):
        return self._search(self.root, val)
 
    def _search(self, node, val):
        if not node:
            return False
        if val == node.val:
            return True
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)
 
    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result
 
    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)
 
tree = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree.insert(v)
 
assert tree.search(6) == True
assert tree.search(5) == False
assert tree.inorder() == [1, 3, 4, 6, 7, 8, 10, 13, 14]  # sorted!

Traversal Orders

Order	Sequence	Use
Inorder (L, Root, R)	Sorted output from BST	Print sorted
Preorder (Root, L, R)	Copy tree structure	Serialization
Postorder (L, R, Root)	Delete tree bottom-up	Cleanup
Level-order	BFS with queue	Breadth-first problems

Balanced Trees

Unbalanced BSTs degrade to O(n). Self-balancing variants fix this:

• AVL tree — strictly balanced (height diff ⇐ 1)
• Red-black tree — approximately balanced (used in Java TreeMap, C++ std::map)
• B-tree — used in databases and file systems

Related

• Recursion — tree operations are naturally recursive
• Heaps — special kind of binary tree
• Graphs — trees are acyclic connected graphs
• BFS and DFS — tree traversal algorithms
• Indexing — B-trees for database indexes