RugvAI Labs

Trees & BST, Part 1: Binary Trees & Traversals

The HTML DOM is a tree. Every JSON document is a tree. File systems are trees. Decision trees in ML are trees. Trees are not an "interview topic" — they're how hierarchical data is stored everywhere. Part 1 builds the foundation: terminology, TreeNode, BST insert/search, and the four traversals every tree problem builds on. Part 2 covers BST deletion, validation, balanced trees, and the Trie.

Learning Objectives

After this lesson, you will be able to:

Command every tree term: root, leaf, height, depth, subtree, degree — and know exactly how to compute them
Implement a TreeNode and a BST with insert, search, and min/max
Apply all four traversals (inorder, preorder, postorder, BFS) both recursively and iteratively
Choose the right traversal for the task: sorted output, reconstruction, deletion order, shortest path

Prerequisites

Before You Start

Review

#Tree Terminology: The Vocabulary You Must Own

Why

Why This Matters

Trees model hierarchy. File systems, organization charts, HTML DOM, parse trees, decision trees in ML all share the same tree shape
BST search beats linear search. O(log n) average vs O(n), the same gain as binary search on a sorted array, but with dynamic insertion and deletion
Traversal order determines output semantics. Inorder gives sorted output from a BST; postorder naturally evaluates expression trees; preorder serializes a tree in a way that allows perfect reconstruction
Tries dominate string operations. Autocomplete, spell check, and IP routing all rely on trie structures that would be impractical with hash maps or sorted arrays
When you need a sorted dynamic sequence in Python, sortedcontainers.SortedList gives you O(log n) search and fast insertion — notably without using a balanced BST at all, which is a good reminder that the guarantee matters more than the structure

#Core Vocabulary

Consider this tree:

Tree Terminology Example

A (root)

B (internal)

D (leaf)

E (leaf)

C (internal)

F (leaf)

Term	Definition	In the tree above
Root	Top node with no parent	A
Leaf	Node with no children	D, E, F
Internal node	Node with at least one child	A, B, C
Parent	Direct predecessor	A is parent of B and C
Children	Direct successors	B and C are children of A
Sibling	Nodes sharing the same parent	B and C are siblings
Subtree	A node plus all its descendants	B's subtree is

pythonrunnable cell

def height(root) -> int:
    """Recursive height computation. O(n) — must visit every node."""
    if root is None:
        return -1   # height of empty tree is -1 by convention
    return 1 + max(height(root.left), height(root.right))

def depth(root, target, current_depth: int = 0) -> int:
    """Find depth of the node containing target value."""
    if root is None:
        return -1
    if root.val == target:
        return current_depth
    left = depth(root.left, target, current_depth + 1)
    if left != -1:
        return left
    return depth(root.right, target, current_depth + 1)

Binary Search Tree — Insert, Search, Traverse & VisualizeInteractive

Insert values and watch BST ordering enforce itself. Step through all four traversals (inorder, preorder, postorder, BFS) with each node lit up as it is visited.

Loading visualization...

What Do You Think?

In a perfectly balanced binary tree with 15 nodes (4 levels: 1 + 2 + 4 + 8 nodes), what is the height?

The height is 3. Height counts edges, not nodes. Root is at depth 0, leaves are at depth 3 — the root-to-leaf path has 3 edges. A balanced tree with height h holds between 2^h and 2^(h+1) − 1 nodes.

#Binary Tree Implementation

A binary tree node holds a value plus references to at most two children:

pythonrunnable cell

from __future__ import annotations
from typing import Any, Optional, List
from collections import deque


class TreeNode:
    """A node in a binary tree."""

    def __init__(self, val: Any) -> None:
        self.val = val
        self.left: Optional[TreeNode] = None
        self.right: Optional[TreeNode] = None

    def __repr__(self) -> str:
        return f"TreeNode({self.val!r})"

    def is_leaf(self) -> bool:
        """A leaf node has no children."""
        return self.left is None and self.right is None


class BinaryTree:
    """
    General binary tree with breadth-first insertion.
    (BST, covered in Section 4, uses a different ordered insert.)
    """

    def __init__(self) -> None:
        self.root: Optional[TreeNode] = None

    def insert(self, val: Any) -> None:
        """
        Insert a value using BFS (level-order) insertion.
        Fills left child first, then right, level by level.
        O(n) in the worst case.
        """
        new_node = TreeNode(val)
        if self.root is None:
            self.root = new_node
            return

        # BFS to find the first node with a free child slot
        queue = deque([self.root])
        while queue:
            node = queue.popleft()
            if node.left is None:
                node.left = new_node
                return
            else:
                queue.append(node.left)
            if node.right is None:
                node.right = new_node
                return
            else:
                queue.append(node.right)

    def height(self) -> int:
        """Height of the tree. O(n) — visits every node."""
        def _height(node: Optional[TreeNode]) -> int:
            if node is None:
                return -1
            return 1 + max(_height(node.left), _height(node.right))
        return _height(self.root)

    def count_nodes(self) -> int:
        """Count all nodes recursively. O(n)."""
        def _count(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            return 1 + _count(node.left) + _count(node.right)
        return _count(self.root)

    def count_leaves(self) -> int:
        """Count leaf nodes. O(n)."""
        def _leaves(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            if node.is_leaf():
                return 1
            return _leaves(node.left) + _leaves(node.right)
        return _leaves(self.root)

Loading visualization...

#Tree Traversals: Four Ways to Visit Every Node

Traversal order fundamentally changes what the output means. There are four standard traversals:

Example Tree Used Throughout This Section

#DFS: Three Orders (Recursive)

pythonreference · read-only

def inorder(root: Optional[TreeNode]) -> List[Any]:
    """
    Left -> Root -> Right.
    Produces SORTED output for a BST — extremely useful.
    Think: 'visit the left subtree completely, then self, then right.'
    """
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)
    # For the example tree: [1, 2, 3, 4, 5, 6, 7]


def preorder(root: Optional[TreeNode]) -> List[Any]:
    """
    Root -> Left -> Right.
    Root is processed BEFORE its subtrees.
    Use case: copy/serialize a tree (preorder gives you insertion order
    to reconstruct the same BST shape from scratch).
    """
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)
    # For the example tree: [4, 2, 1, 3, 6, 5, 7]


def postorder(root: Optional[TreeNode]) -> List[Any]:
    """
    Left -> Right -> Root.
    Root is processed AFTER both subtrees.
    Use case: (1) delete a tree (free children before parent),
              (2) evaluate expression trees (compute sub-expressions first).
    """
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]
    # For the example tree: [1, 3, 2, 5, 7, 6, 4]

#BFS: Level-Order Traversal

pythonreference · read-only

def level_order(root: Optional[TreeNode]) -> List[List[Any]]:
    """
    Visit nodes level by level, left to right.
    Returns a list of levels — each level is a list of values.
    Use case: shortest path in unweighted trees, printing tree structure,
    finding minimum depth.

    Uses a queue (deque) — never use recursion for BFS.
    """
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)     # snapshot: how many nodes at this level
        level_values = []

        for _ in range(level_size):
            node = queue.popleft()
            level_values.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_values)

    return result
    # For the example tree: [[4], [2, 6], [1, 3, 5, 7]]

#Iterative DFS: Using an Explicit Stack

Recursive DFS is elegant but uses O(h) call stack space (dangerous for deep trees). Here are the iterative versions:

pythonreference · read-only

from collections import deque

def inorder_iterative(root: Optional[TreeNode]) -> List[Any]:
    """
    Iterative inorder (Left -> Root -> Right).
    Uses an explicit stack. Critical for very deep trees (no recursion limit).
    """
    result = []
    stack = []
    current = root

    while current is not None or stack:
        # Go as far left as possible, pushing nodes onto the stack
        while current is not None:
            stack.append(current)
            current = current.left

        # Process the node (it has no more left children to push)
        current = stack.pop()
        result.append(current.val)

        # Move to the right subtree
        current = current.right

    return result


def preorder_iterative(root: Optional[TreeNode]) -> List[Any]:
    """
    Iterative preorder (Root -> Left -> Right).
    Push right child first so left is processed first (stack is LIFO).
    """
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)        # process root
        if node.right:
            stack.append(node.right)   # right pushed first (processed second)
        if node.left:
            stack.append(node.left)    # left pushed second (processed first)

    return result


def postorder_iterative(root: Optional[TreeNode]) -> List[Any]:
    """
    Iterative postorder (Left -> Right -> Root).
    Trick: do a modified preorder (Root -> Right -> Left), then reverse the result.
    """
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)    # left pushed first (reversed later)
        if node.right:
            stack.append(node.right)   # right pushed second

    return result[::-1]   # reverse gives Left -> Right -> Root

#Comparing Traversal Outputs

Traversal Comparison Tree

Traversal Outputs

Traversal	Output	Key Property
Inorder	[1, 2, 3, 4, 5, 6, 7]	SORTED (BST property)
Preorder	[4, 2, 1, 3, 6, 5, 7]	Root first (insertion order)
Postorder	[1, 3, 2, 5, 7, 6, 4]	Root last (children first)
BFS	[[4], [2,6], [1,3,5,7]]	Level by level

Choosing the right traversal

Task	Best Traversal
Get sorted values from BST	Inorder
Copy/reconstruct the tree	Preorder
Delete all nodes (free memory)	Postorder
Find minimum path between nodes	BFS (level-order)
Evaluate an expression tree	Postorder
Find all leaf nodes	Any DFS
Serialize/deserialize	BFS or preorder

In-order traversal of a small BST — left, visit, right

Step 0 / 14

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    visit(node.val)
    inorder(node.right)

Call stack

empty

1 / 15

The visit order is the post-return sequence: 1, 2, 3 — the sorted output. Inorder always recurses into the left subtree first, then visits the current node, then recurses into the right subtree. For a BST, this guarantees sorted output.

#Binary Search Tree: Full Implementation

The BST property: for every node n, all values in n.left subtree are strictly less than n.val, and all values in n.right subtree are strictly greater.

BST with values [5, 3, 7, 1, 4, 6, 8]

BST property check at node 5: All values in left subtree (3, 1, 4) < 5. All values in right subtree (7, 6, 8) > 5.

pythonrunnable cell

from __future__ import annotations
from typing import Any, List, Optional, Tuple


class BSTNode:
    """Node for a Binary Search Tree."""

    def __init__(self, val: Any) -> None:
        self.val = val
        self.left: Optional[BSTNode] = None
        self.right: Optional[BSTNode] = None


class BST:
    """
    Binary Search Tree.

    Average-case O(log n) insert/search/delete for balanced trees.
    Worst-case O(n) when tree degenerates (see Section 5).
    Inorder traversal always returns a sorted sequence.
    """

    def __init__(self) -> None:
        self.root: Optional[BSTNode] = None
        self._size: int = 0

    # ------------------------------------------------------------------
    # Insert
    # ------------------------------------------------------------------

    def insert(self, val: Any) -> None:
        """
        Insert a value into the BST.
        Navigates left if val < current, right if val > current.
        Ignores duplicate values (set semantics).
        O(h) where h is the tree height.
        """
        self.root = self._insert_recursive(self.root, val)

    def _insert_recursive(self, node: Optional[BSTNode], val: Any) -> BSTNode:
        """
        Returns the (possibly new) root of the subtree.
        THE KEY PATTERN: node.left = _insert(node.left, val)
        — always reassign because when node is None we return a new BSTNode.
        """
        if node is None:
            self._size += 1
            return BSTNode(val)   # base case: found the insertion spot
        if val < node.val:
            node.left = self._insert_recursive(node.left, val)
        elif val > node.val:
            node.right = self._insert_recursive(node.right, val)
        # val == node.val: duplicate — do nothing (BSTs typically store unique values)
        return node

    def insert_iterative(self, val: Any) -> None:
        """Iterative insert — avoids recursion overhead for very deep trees."""
        new_node = BSTNode(val)
        if self.root is None:
            self.root = new_node
            self._size += 1
            return

        current = self.root
        while True:
            if val < current.val:
                if current.left is None:
                    current.left = new_node
                    self._size += 1
                    return
                current = current.left
            elif val > current.val:
                if current.right is None:
                    current.right = new_node
                    self._size += 1
                    return
                current = current.right
            else:
                return   # duplicate

Loading visualization...

pythonreference · read-only

    # ------------------------------------------------------------------
    # Search
    # ------------------------------------------------------------------

    def search(self, val: Any) -> bool:
        """Return True if val is in the BST. O(h)."""
        return self._search_recursive(self.root, val)

    def _search_recursive(self, node: Optional[BSTNode], val: Any) -> bool:
        if node is None:
            return False
        if val == node.val:
            return True
        if val < node.val:
            return self._search_recursive(node.left, val)
        return self._search_recursive(node.right, val)

    def search_iterative(self, val: Any) -> bool:
        """Iterative search — O(h), O(1) space."""
        current = self.root
        while current is not None:
            if val == current.val:
                return True
            current = current.left if val < current.val else current.right
        return False

Quick check

Which property must every node in a Binary Search Tree satisfy?

pythonreference · read-only

    # ------------------------------------------------------------------
    # Min and Max
    # ------------------------------------------------------------------

    def min_value(self) -> Any:
        """
        Minimum value is always at the leftmost node.
        Keep going left until left is None.
        O(h).
        """
        if self.root is None:
            raise ValueError("BST is empty")
        node = self.root
        while node.left is not None:
            node = node.left
        return node.val

    def max_value(self) -> Any:
        """Maximum is at the rightmost node. O(h)."""
        if self.root is None:
            raise ValueError("BST is empty")
        node = self.root
        while node.right is not None:
            node = node.right
        return node.val

    def _min_node(self, node: BSTNode) -> BSTNode:
        """Helper: return the node with minimum value in a subtree."""
        while node.left is not None:
            node = node.left
        return node


    # ------------------------------------------------------------------
    # Traversals
    # ------------------------------------------------------------------

    def inorder(self) -> List[Any]:
        """Returns a SORTED list of all values. O(n)."""
        result: List[Any] = []
        def _inorder(node: Optional[BSTNode]) -> None:
            if node is None:
                return
            _inorder(node.left)
            result.append(node.val)
            _inorder(node.right)
        _inorder(self.root)
        return result

    # ------------------------------------------------------------------
    # Utilities
    # ------------------------------------------------------------------

    def __len__(self) -> int:
        return self._size

    def __contains__(self, val: Any) -> bool:
        return self.search(val)

    def __repr__(self) -> str:
        return f"BST(inorder={self.inorder()})"

#BST Time Complexity

Operation	Average (balanced)	Worst Case (degenerate)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Min / Max	O(log n)	O(n)
Inorder (all)	O(n)	O(n)

#The Degenerate Case: Why Worst-Case Is O(n)

Insert values in sorted order: 1, 2, 3, 4, 5:

Degenerate BST — Inserting [1, 2, 3, 4, 5] in Order

This is just a linked list. Height = n - 1 = 4. Searching for 5: traverse 5 nodes -- O(n), not O(log n).

Compare to inserting [3, 1, 4, 2, 5] — same values, different order:

Balanced BST — Inserting [3, 1, 4, 2, 5]

Height = 2. Searching for 5: 3 comparisons -- O(log n).

The fix: Self-Balancing Trees. AVL trees and Red-Black trees automatically restructure on every insert/delete to keep the height at O(log n), guaranteeing worst-case O(log n) operations. See the DeepDive at the end of this lesson.

pythonreference · read-only

# In production Python, use sortedcontainers for a balanced sorted structure:
from sortedcontainers import SortedList

sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6])
sl.add(7)                      # O(log n) insert maintaining sorted order
print(sl)                      # SortedList([1, 1, 2, 3, 4, 5, 6, 7, 9])
print(sl.bisect_left(5))       # O(log n) binary search → index 5
sl.discard(4)                  # O(log n) delete
print(sl[2])                   # O(log n) index access

#Interactive Visualization: Tree Operations & Traversals

Build BSTs interactively, watch all four traversal orders animate, and explore Trie prefix matching:

Loading visualization...

#Code Playground

pythonplayground.py · Pyodide

class BSTNode:
  def __init__(self, val):
      self.val = val
      self.left = None
      self.right = None

class BST:
  def __init__(self):
      self.root = None

def insert(self, val):
      # TODO: Insert val, maintaining the BST property.
      # Use the recursive pattern: node.left = _insert(node.left, val)
      # Return the node from the recursive helper so the tree is linked.
      self.root = self._insert(self.root, val)

def _insert(self, node, val):
      # TODO: Base case returns a new BSTNode(val).
      # Recursive case: go left if val &lt; node.val, right otherwise.
      # Must return node at the end so parent links are maintained.
      pass

def search(self, val):
      # TODO: Return True if val is in the tree, False otherwise.
      # Iterative version: compare val to current.val to go left or right.
      pass

def inorder(self):
      # TODO: Return sorted list of all values using inorder traversal.
      result = []
      # Hint: nested helper function that appends to result
      return result

# Test your implementation
bst = BST()
for val in [5, 3, 7, 1, 4, 6, 8]:
  bst.insert(val)

print(bst.inorder())   # Expected: [1, 3, 4, 5, 6, 7, 8]
print(bst.search(4))   # Expected: True
print(bst.search(9))   # Expected: False

Tests · assert bst.inorder() == [1, 3, 4, 5, 6, 7, 8]; assert bst.search(4) == True; assert bst.search(9) == False

Intuition

Build Your Intuition

A balanced tree is wide and shallow. An unbalanced tree is tall and thin — secretly a linked list.

A BST with n nodes has height O(log n) when balanced and O(n) when degenerate (sorted insertions). The difference is enormous:

pythonreference · read-only

# Balanced BST with 1,000,000 nodes:
#   height ≈ log2(1,000,000) ≈ 20
#   search: ~20 comparisons

# Degenerate BST (insert 1, 2, 3, ..., 1,000,000 in sorted order):
#   height = 999,999
#   search: up to 1,000,000 comparisons — same as linear search!

# The shape of the tree is determined by INSERTION ORDER, not values:
bst = BST()
for v in [4, 2, 6, 1, 3, 5, 7]:   # balanced: height = 2
    bst.insert(v)

bst2 = BST()
for v in [1, 2, 3, 4, 5, 6, 7]:   # degenerate: height = 6 (linked list)
    bst2.insert(v)

This is why self-balancing trees (AVL, Red-Black) exist — they restructure after every insert/delete to keep height at O(log n) regardless of insertion order. In Python, use sortedcontainers.SortedList which achieves the same guarantee without implementing rotations yourself.

#Key Takeaways

BST invariant is the entire data structure: every left descendant < root < every right descendant; violate it once and all O(log n) guarantees break
Four traversals encode four different meanings: inorder → sorted output; preorder → tree reconstruction; postorder → process children before parent; level-order → shortest path, BFS problems
The recursive insert pattern: node.left = self._insert(node.left, val) — always reassign because the base case returns a fresh node, and always return node at the end of the helper
Unbalanced BSTs degrade to O(n): inserting sorted data creates a linked list — use sortedcontainers.SortedList when you need dependable O(log n) lookups in production Python code
Recursive DFS + iterative BFS covers ~90% of tree interview problems: internalize the recursive DFS template (base case, left recursion, right recursion, return value) and the BFS deque loop before any tree interview

#Quiz

Quick Check1 / 4

You perform an inorder traversal of a BST and get [1, 2, 3, 5, 7, 8]. Which value was most recently deleted from the original BST if it contained [1, 2, 3, 4, 5, 7, 8]?

Your Reflection

Continue Learning

Discussion

Trees & BST, Part 1: Binary Trees & Traversals

After this lesson, you will be able to:

Before You Start

#Tree Terminology: The Vocabulary You Must Own

#Core Vocabulary

#Binary Tree Implementation

#Tree Traversals: Four Ways to Visit Every Node

#DFS: Three Orders (Recursive)

#BFS: Level-Order Traversal

#Iterative DFS: Using an Explicit Stack

#Comparing Traversal Outputs

Choosing the right traversal

In-order traversal of a small BST — left, visit, right

#Binary Search Tree: Full Implementation

#BST Time Complexity

#The Degenerate Case: Why Worst-Case Is O(n)

#Interactive Visualization: Tree Operations & Traversals

#Code Playground

#Key Takeaways

#Quiz