Binary Trees and BST

Arrays and linked lists are linear — one thing after another. A tree breaks that: each node can branch into multiple children, giving you hierarchy. Trees are everywhere in interviews: file systems, DOM, database indexes, and a huge share of “medium” LeetCode problems.

What you’ll learn

Core vocabulary: root, leaf, height, depth, subtree.
A minimal TreeNodeTreeNode class — the shape every tree problem starts from.
The three depth-first traversal orders, recursive and iterative.
Level-order (breadth-first) traversal with collections.dequecollections.deque.
The Binary Search Tree (BST) property, and why its inorder traversal comes out sorted for free.

Tree terminology

Root — the single top node with no parent.
Leaf — a node with no children.
Depth of a node — number of edges from the root down to it.
Height of a tree — the depth of its deepest leaf (height of an empty tree is usually defined as $-1$ , height of a single node is $0$ ).
Subtree — any node plus everything hanging below it, treated as its own tree.
Binary tree — every node has at most two children, conventionally called leftleft and rightright.

diagram A small binary tree mermaid

  graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> F((14))
    E --> G((4))
    E --> H((7))

Here 88 is the root, 11, 44, 77, and 1414 are leaves, and the height of the whole tree is 22 (root at depth 0, deepest leaves at depth 2).

The `TreeNodeTreeNode` class

Almost every tree problem — on LeetCode and in interviews — hands you (or asks you to build) exactly this shape:

tree_node.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
# Build the tree from the diagram above by hand
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
print("root value:", root.val)
print("left child of root:", root.left.val)
print("right child of root:", root.right.val)

tree_node.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
# Build the tree from the diagram above by hand
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
print("root value:", root.val)
print("left child of root:", root.left.val)
print("right child of root:", root.right.val)

Depth-first traversals (recursive)

There are three natural orders to visit (node, left, right)(node, left, right), depending on when you visit the node itself:

dfs_recursive.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def preorder(node, out):
    # node -> left -> right
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
 
 
def inorder(node, out):
    # left -> node -> right
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
def postorder(node, out):
    # left -> right -> node
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)
 
 
pre, inn, post = [], [], []
preorder(root, pre)
inorder(root, inn)
postorder(root, post)
print("preorder :", pre)
print("inorder  :", inn)
print("postorder:", post)

dfs_recursive.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def preorder(node, out):
    # node -> left -> right
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
 
 
def inorder(node, out):
    # left -> node -> right
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
def postorder(node, out):
    # left -> right -> node
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)
 
 
pre, inn, post = [], [], []
preorder(root, pre)
inorder(root, inn)
postorder(root, post)
print("preorder :", pre)
print("inorder  :", inn)
print("postorder:", post)

Depth-first traversals (iterative, with an explicit stack)

Recursion is just the call stack doing the bookkeeping for you. Swap it for your own listlist-as-stack and you get the same order without recursion depth risk:

dfs_iterative.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def preorder_iterative(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        # push right FIRST so left is processed first (stack = LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
 
 
def inorder_iterative(root):
    out, stack = [], []
    cur = root
    while cur or stack:
        while cur:            # walk all the way left, stacking as we go
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()     # leftmost unvisited node
        out.append(cur.val)
        cur = cur.right       # then explore its right subtree
    return out
 
 
print("preorder (iterative):", preorder_iterative(root))
print("inorder (iterative): ", inorder_iterative(root))

dfs_iterative.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def preorder_iterative(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        # push right FIRST so left is processed first (stack = LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
 
 
def inorder_iterative(root):
    out, stack = [], []
    cur = root
    while cur or stack:
        while cur:            # walk all the way left, stacking as we go
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()     # leftmost unvisited node
        out.append(cur.val)
        cur = cur.right       # then explore its right subtree
    return out
 
 
print("preorder (iterative):", preorder_iterative(root))
print("inorder (iterative): ", inorder_iterative(root))

Level-order traversal (BFS) with a deque

Depth-first goes deep before wide; level-order visits every node one level at a time, using a queue (collections.dequecollections.deque for $O(1)$ pops from the front):

level_order.py

from collections import deque
 
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_vals = []
        for _ in range(level_size):
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)
    return result
 
 
print(level_order(root))   # one list per depth level

level_order.py

from collections import deque
 
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
root = TreeNode(8,
    TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
    TreeNode(10, None, TreeNode(14)))
 
 
def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_vals = []
        for _ in range(level_size):
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)
    return result
 
 
print(level_order(root))   # one list per depth level

Binary Search Trees (BST)

A BST adds one ordering rule to every node: everything in the left subtree is smaller, everything in the right subtree is larger.

\text{left subtree} < \text{node.val} < \text{right subtree}

That single rule makes search and insert run in $O(h)$ , where $h$ is the tree’s height — $O(\log n)$ if the tree stays roughly balanced, but $O(n)$ if it degenerates into a chain (more on that next lesson).

bst_search_insert.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def bst_insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    elif val > root.val:
        root.right = bst_insert(root.right, val)
    return root   # duplicate values: no-op
 
 
def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    return bst_search(root.left, target) if target < root.val else bst_search(root.right, target)
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7]:
    root = bst_insert(root, v)
 
print("search 6: ", bst_search(root, 6))
print("search 99:", bst_search(root, 99))
 
sorted_out = []
inorder(root, sorted_out)
print("inorder (sorted!):", sorted_out)

bst_search_insert.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def bst_insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    elif val > root.val:
        root.right = bst_insert(root.right, val)
    return root   # duplicate values: no-op
 
 
def bst_search(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    return bst_search(root.left, target) if target < root.val else bst_search(root.right, target)
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7]:
    root = bst_insert(root, v)
 
print("search 6: ", bst_search(root, 6))
print("search 99:", bst_search(root, 99))
 
sorted_out = []
inorder(root, sorted_out)
print("inorder (sorted!):", sorted_out)

Complexity at a glance

Operation	Average (balanced)	Worst case (skewed)
Search	$O(\log n)$	$O(n)$
Insert	$O(\log n)$	$O(n)$
Traversal (any order)	$O(n)$	$O(n)$
Space (recursive traversal)	$O(h)$ call stack	$O(n)$ call stack

LeetCode problem set

#	Problem	Difficulty	The twist
104	Maximum Depth of Binary Tree	Easy	One line of recursion: `1 + max(depth(left), depth(right))1 + max(depth(left), depth(right))`
98	Validate Binary Search Tree	Medium	Don’t just compare a node to its children; carry a `(low, high)(low, high)` bound down the recursion
102	Binary Tree Level Order Traversal	Medium	The deque pattern above, verbatim
235	Lowest Common Ancestor of a Binary Search Tree	Medium	Use the BST property to decide “go left / go right / this is it” in $O(h)$ without visiting every node

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 104 — Maximum Depth of Binary Tree · Easy

Problem. Return the number of nodes along the longest path from the root down to the farthest leaf.

Constraints. 0 <= number of nodes <= 10^40 <= number of nodes <= 10^4, -100 <= Node.val <= 100-100 <= Node.val <= 100.

Examples. [3,9,20,null,null,15,7][3,9,20,null,null,15,7] gives 33 · [1,null,2][1,null,2] gives 22 · [][] gives 00

Editorial

The base case handles the empty tree, and the recursive case combines what the children report. This is the canonical ”return a value upward” tree recursion.

Time $O(n)$ . Space $O(h)$ for the recursion — $O(\log n)$ balanced, $O(n)$ degenerate.

Contrast with minimum depth (LC 111), where the analogous 1 + min(left, right)1 + min(left, right) is wrong: a node with one child would report a depth through its missing side. Maximum depth has no such trap, which is exactly why the two problems are usually taught together — see Tree BFS.

Follow-ups: “Iteratively?” — BFS counting levels, or DFS with an explicit stack of (node, depth)(node, depth). “Minimum depth?” — BFS with an early exit on the first leaf. “Diameter (LC 543)?” — the split-brain trick: return the height, record left + rightleft + right. “10^4 nodes in a chain?” — exceeds Python’s recursion limit; go iterative or raise it.

LC 226 — Invert Binary Tree · Easy

Problem. Invert the tree — mirror it left-to-right — and return the root.

Constraints. 0 <= number of nodes <= 1000 <= number of nodes <= 100.

Examples. [4,2,7,1,3,6,9][4,2,7,1,3,6,9] gives [4,7,2,9,6,3,1][4,7,2,9,6,3,1] · [2,1,3][2,1,3] gives [2,3,1][2,3,1] · [][] gives [][]

Editorial

Swap at every node and recurse. The traversal order does not matter — pre-order, post-order and BFS all work, because each node’s swap is independent of the others.

Time $O(n)$ . Space $O(h)$ .

The single-line swap relies on Python evaluating the whole right-hand side before assigning. Written imperatively you would need a temporary:

python

temp = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(temp)      # temp, NOT root.left

python

temp = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(temp)      # temp, NOT root.left

Forgetting the temporary — recursing into root.leftroot.left after overwriting it — silently produces a wrong tree, which is the one real trap in an otherwise trivial problem.

Follow-ups: “Iteratively?” — BFS with a queue, swapping each dequeued node’s children. “Check whether a tree is symmetric (LC 101)?” — next problem; compare the tree against its own mirror rather than mutating it. “Without mutating the input?” — build a new tree, returning fresh nodes with the children swapped.

LC 101 — Symmetric Tree · Easy

Problem. Return TrueTrue if the tree is a mirror image of itself around its centre.

Constraints. 1 <= number of nodes <= 10001 <= number of nodes <= 1000.

Examples. [1,2,2,3,4,4,3][1,2,2,3,4,4,3] gives TrueTrue · [1,2,2,null,3,null,3][1,2,2,null,3,null,3] gives FalseFalse

Editorial

Symmetry is a relation between two subtrees, so the helper takes two arguments. Passing (root, root)(root, root) starts the comparison of the tree against itself.

Time $O(n)$ . Space $O(h)$ .

The crossing is everything: mirror(a.left, b.right)mirror(a.left, b.right) pairs the outermost nodes, and mirror(a.right, b.left)mirror(a.right, b.left) pairs the inner ones. Writing mirror(a.left, b.left)mirror(a.left, b.left) would test whether the tree equals itself — trivially TrueTrue — and pass every input.

[1,2,2,null,3,null,3][1,2,2,null,3,null,3] is the discriminating case: the values are symmetric but the shape is not. Both 22s have only a right child, so the mirror pairing hits NoneNone against a node.

This is the same parallel recursion as Same Tree, with the child arguments swapped — worth pointing out, since the two problems share a skeleton.

Follow-ups: “Iteratively?” — a queue of pairs, enqueuing (a.left, b.right)(a.left, b.right) and (a.right, b.left)(a.right, b.left). “Same tree (LC 100)?” — the uncrossed version. “Invert then compare?” — works, but it mutates the input and costs an extra pass.

Recap

Trees generalize linked lists into a hierarchy; TreeNodeTreeNode with leftleft/rightright is the universal building block.
Preorder/inorder/postorder are the same recursive shape with the “visit” step moved; both recursive and iterative (explicit stack) versions matter.
Level-order needs a dequedeque for $O(1)$ front-pops — never list.pop(0)list.pop(0).
A BST’s ordering rule gives $O(h)$ search/insert and a free sorted output via inorder traversal — but only if the tree stays balanced.

Next: Balanced Trees Overview — why an unbalanced BST degrades to $O(n)$ , and how AVL/Red-Black trees keep height at $O(\log n)$ .

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Binary Trees and BST

What you’ll learn

Tree terminology

The TreeNodeTreeNode class

Depth-first traversals (recursive)

Depth-first traversals (iterative, with an explicit stack)

Level-order traversal (BFS) with a deque

Binary Search Trees (BST)

Complexity at a glance

LeetCode problem set

Practice — real LeetCode problems

LC 104 — Maximum Depth of Binary Tree · Easy

LC 226 — Invert Binary Tree · Easy

LC 101 — Symmetric Tree · Easy

Recap

Was this page helpful?

The `TreeNodeTreeNode` class