10. Trees and BSTs

📋 Jump to Takeaways

Trees model hierarchical relationships. File systems, HTML documents, organization charts, decision processes — anything with a parent-child structure is a tree. In DSA, binary trees and binary search trees are the foundation for heaps, tries, segment trees, and most divide-and-conquer algorithms.

The Structure

A tree is a connected graph with no cycles. One node is the root. Every other node has exactly one parent and zero or more children.

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

//       5
//      / \
//     3   8
//    / \   \
//   1   4   9

Binary tree — each node has at most two children (left and right). Most interview problems use binary trees.

Terminology: root (top node), leaf (no children), depth (distance from root), height (longest path to a leaf).

Binary Tree Types

Type	Definition
Full	Every node has 0 or 2 children (no single-child nodes)
Complete	All levels fully filled except possibly the last, which fills left to right
Perfect	All internal nodes have 2 children and all leaves are at the same depth
Balanced	Height difference between left and right subtrees is at most 1 for every node
BST	For every node, all left descendants are smaller and all right descendants are larger

Traversals

Four ways to visit every node. Each produces a different order:

// Inorder: left → root → right (gives sorted order for BSTs)
func inorder(root *TreeNode) {
    if root == nil {
        return
    }
    inorder(root.Left)
    fmt.Println(root.Val) // process
    inorder(root.Right)
}

// Preorder: root → left → right (copy/serialize a tree)
func preorder(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Println(root.Val) // process
    preorder(root.Left)
    preorder(root.Right)
}

// Postorder: left → right → root (delete a tree, evaluate expressions)
func postorder(root *TreeNode) {
    if root == nil {
        return
    }
    postorder(root.Left)
    postorder(root.Right)
    fmt.Println(root.Val) // process
}

// Level-order (BFS): level by level, left to right
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var result [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        level := []int{}
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

DFS Patterns on Trees

Most tree problems are recursive DFS. The pattern: solve for left subtree, solve for right subtree, combine.

// Max depth — O(n)
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    return max(left, right) + 1
}

// Check if symmetric
func isSymmetric(root *TreeNode) bool {
    return isMirror(root.Left, root.Right)
}

func isMirror(a, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    return a.Val == b.Val &&
        isMirror(a.Left, b.Right) &&
        isMirror(a.Right, b.Left)
}

Iterative DFS

Recursive DFS uses the call stack implicitly. Iterative DFS uses an explicit stack — useful when recursion depth could overflow or when you need more control.

// Iterative inorder traversal — O(n) time, O(h) space
func inorderIterative(root *TreeNode) []int {
    var result []int
    stack := []*TreeNode{}
    curr := root
    for curr != nil || len(stack) > 0 {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left // push all lefts
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1] // pop
        result = append(result, curr.Val)
        curr = curr.Right
    }
    return result
}

The pattern: push all left children, pop and process, then go right. This gives sorted order for BSTs and is the basis for BST iterators.

Lowest Common Ancestor (LCA)

The LCA of two nodes is the deepest node that is an ancestor of both. It's where the paths from root to each node diverge.

LeetCode 236 - Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor of two given nodes.

// LCA in a binary tree — O(n)
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root // p and q are on different sides
    }
    if left != nil {
        return left
    }
    return right
}

In a BST, LCA is simpler — use the BST property to decide which direction to go:

// LCA in a BST — O(log n)
func lcaBST(root, p, q *TreeNode) *TreeNode {
    for root != nil {
        if p.Val < root.Val && q.Val < root.Val {
            root = root.Left
        } else if p.Val > root.Val && q.Val > root.Val {
            root = root.Right
        } else {
            return root // split point
        }
    }
    return nil
}

Binary Search Trees

A BST adds one rule: for every node, all values in the left subtree are smaller, all values in the right subtree are larger. This gives O(log n) search, insert, and delete — if the tree is balanced.

// Search in BST — O(log n) average, O(n) worst (skewed)
func search(root *TreeNode, target int) *TreeNode {
    if root == nil || root.Val == target {
        return root
    }
    if target < root.Val {
        return search(root.Left, target)
    }
    return search(root.Right, target)
}

// Insert into BST — O(log n) average
func insert(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insert(root.Left, val)
    } else {
        root.Right = insert(root.Right, val)
    }
    return root
}

Inorder traversal of a BST gives sorted order. This is the key property — if you need the kth smallest element, do inorder and count.

LeetCode 230 - Kth Smallest Element in a BST

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    curr := root
    for curr != nil || len(stack) > 0 {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return curr.Val
        }
        curr = curr.Right
    }
    return -1
}

Iterative inorder traversal — visit nodes in sorted order, return the kth one. O(H + k) where H is tree height.

BST Deletion

Deleting from a BST has three cases:

Leaf node — just remove it
One child — replace node with its child
Two children — replace with inorder successor (smallest in right subtree), then delete the successor

LeetCode 450 - Delete Node in a BST

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        // Found the node to delete
        if root.Left == nil {
            return root.Right // case 1 & 2
        }
        if root.Right == nil {
            return root.Left // case 2
        }
        // Case 3: find inorder successor (min of right subtree)
        successor := root.Right
        for successor.Left != nil {
            successor = successor.Left
        }
        root.Val = successor.Val
        root.Right = deleteNode(root.Right, successor.Val)
    }
    return root
}

BST Validation

A common mistake: checking only that left.Val < node.Val < right.Val. This misses cases where a deeper node violates the BST property relative to an ancestor.

The correct approach passes a valid range down:

LeetCode 98 - Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid BST.

func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }
    if node.Val <= min || node.Val >= max {
        return false
    }
    return validate(node.Left, min, node.Val) &&
        validate(node.Right, node.Val, max)
}

Each node must be within the range defined by all its ancestors, not just its immediate parent.

Balanced vs Unbalanced

A balanced BST has height O(log n). An unbalanced BST (inserting sorted data) degrades to a linked list with height O(n).

Balanced (height 3):     Unbalanced (height 5):
       4                  1
      / \                  \
     2   6                  2
    / \ / \                  \
   1  3 5  7                  3
                               \
                                4
                                 \
                                  5

Self-balancing trees (AVL, Red-Black) maintain O(log n) height automatically. You rarely implement these — but you should know they exist and that Go's standard library doesn't include one (use a sorted slice or third-party package).

Operation Costs

Operation	BST (balanced)	BST (worst)	Hash Map
Search	O(log n)	O(n)	O(1)
Insert	O(log n)	O(n)	O(1)
Delete	O(log n)	O(n)	O(1)
Min/Max	O(log n)	O(n)	O(n)
Range query	O(log n + k)	O(n)	O(n)
Ordered iteration	O(n)	O(n)	O(n log n)*

*Hash maps need to sort for ordered iteration.

BSTs beat hash maps when you need order: min, max, range queries, predecessor/successor, ordered iteration.

When to Use Trees

Hierarchical data (file systems, DOM, org charts)
Need sorted order with fast insert/delete → BST
Need range queries ("all values between 5 and 10") → BST
Divide-and-conquer algorithms (merge sort is a tree of merges)
Expression parsing and evaluation

When NOT to Use Trees

Just need fast lookup by key → hash map (simpler, faster)
Data is flat with no hierarchy → array or hash map
You need O(1) access by index → array

Practice Problems

Problem	Difficulty	Link
Maximum Depth of Binary Tree	Easy	LeetCode 104
Invert Binary Tree	Easy	LeetCode 226
Validate Binary Search Tree	Medium	LeetCode 98
Binary Tree Level Order Traversal	Medium	LeetCode 102
Lowest Common Ancestor of a BST	Medium	LeetCode 235
Kth Smallest Element in a BST	Medium	LeetCode 230
Delete Node in a BST	Medium	LeetCode 450
Serialize and Deserialize Binary Tree	Hard	LeetCode 297

Key Takeaways

Trees model hierarchy; binary trees have at most two children per node
Four traversals: inorder (sorted for BST), preorder (serialize), postorder (delete), level-order (BFS)
Most tree problems are recursive DFS: solve left, solve right, combine
BSTs give O(log n) search/insert/delete when balanced — but degrade to O(n) when skewed
BSTs beat hash maps when you need order, range queries, or min/max
Inorder traversal of a BST produces sorted output