Category 9

Trees & BST

Master tree traversals, binary search trees, and advanced tree patterns including lowest common ancestor, path problems, and tree serialization. Essential for system design and algorithmic problems.

12
Problems
3
Difficulty Levels
100%
Complete Solutions
LeetCode
Curated
Theory

Binary Trees & Binary Search Trees

Trees are non-linear data structures used extensively in databases, file systems, and search algorithms. Understanding traversals and BST properties is fundamental to solving tree problems efficiently.

1. TreeNode Class Definition

The standard tree node representation in C# contains a value and references to left and right children.

csharp 
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

2. DFS Traversals (Recursive)

Depth-first search explores the tree by going as deep as possible before backtracking. Three main orders: inorder, preorder, postorder.

csharp 
// Inorder: Left -> Root -> Right (BST gives sorted order)
void Inorder(TreeNode root, List<int> result) {
    if (root == null) return;
    Inorder(root.left, result);
    result.Add(root.val);
    Inorder(root.right, result);
}

// Preorder: Root -> Left -> Right
void Preorder(TreeNode root, List<int> result) {
    if (root == null) return;
    result.Add(root.val);
    Preorder(root.left, result);
    Preorder(root.right, result);
}

// Postorder: Left -> Right -> Root
void Postorder(TreeNode root, List<int> result) {
    if (root == null) return;
    Postorder(root.left, result);
    Postorder(root.right, result);
    result.Add(root.val);
}

3. BFS / Level-Order Traversal

Breadth-first search explores level by level using a queue. Essential for finding nodes at specific depths and level-order problems.

csharp 
IList<int> LevelOrder(TreeNode root) {
    var result = new List<int>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0) {
        int levelSize = queue.Count;
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.Dequeue();
            result.Add(node.val);
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return result;
}

4. Binary Search Tree Property

In a BST, for any node: all values in the left subtree are strictly less than the node's value, and all values in the right subtree are strictly greater.

💡
Key insight: Inorder traversal of a BST yields sorted values. Use this property to validate BSTs and solve path problems.

5. Common Tree Patterns

Pattern Strategy Time Complexity
Path Problems DFS accumulate path sum, check at leaves or intermediate nodes O(n)
Ancestor Problems Postorder DFS returning matched nodes from both subtrees O(n)
BST Search Compare value with node, go left if smaller, right if larger O(log n) avg, O(n) worst
Serialization Preorder or level-order with markers for null children O(n)
Depth/Height Recursively compute max depth of subtrees O(n)
Problems

12 Tree & BST Problems

1. Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree. Depth is defined as the number of nodes along the longest path from root to any leaf.

★ Easy DFS Recursion
1

Problem Statement

Given a binary tree, find the maximum depth. A leaf node's depth is 1. An empty tree has depth 0.

Example: Tree [3,9,20,null,null,15,7] has depth 3.

Approach

1
Use recursive DFS: base case is null node returns 0.
2
For each node, recursively find max depth of left and right subtrees.
3
Return 1 + max(left_depth, right_depth).

Complete C# Solution

csharp 
// LeetCode 104
public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

h = height; recursion stack depth equals tree height. Balanced tree: O(log n), skewed: O(n).

Edge Cases

  • Null tree: returns 0
  • Single node: returns 1
  • Skewed tree (linked list): O(n) space used
2. Invert Binary Tree

Mirror a binary tree by swapping left and right children at every node.

★ Easy DFS Tree Transformation
2

Problem Statement

Invert a binary tree. All left children become right children and vice versa.

Example: [4,2,7,1,3,6,9] becomes [4,7,2,9,6,3,1].

Approach

1
Use recursive DFS to traverse all nodes.
2
At each node, swap its left and right children.
3
Recursively invert both subtrees and return the node.

Complete C# Solution

csharp 
// LeetCode 226
public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;

        // Swap children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert both subtrees
        InvertTree(root.left);
        InvertTree(root.right);

        return root;
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Must visit every node to swap; recursion depth is tree height.

Edge Cases

  • Null tree: returns null
  • Single node: returns same node (no children to swap)
  • Symmetric tree: becomes symmetric after inversion
3. Same Tree

Check if two binary trees are structurally identical with the same node values.

★ Easy DFS Comparison
3

Problem Statement

Determine if two binary trees are the same. Both structure and values must match.

Approach

1
Base case: both null → true; one null → false.
2
Check if current node values match.
3
Recursively check left and right subtrees simultaneously.

Complete C# Solution

csharp 
// LeetCode 100
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        // Both null
        if (p == null && q == null) return true;

        // One null or values differ
        if (p == null || q == null || p.val != q.val) return false;

        // Recursively check both subtrees
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

Complexity Analysis

Time
O(min(m, n))
Space
O(h)

m, n = sizes of two trees; stops early on mismatch.

Edge Cases

  • Both null: true
  • One null: false
  • Same structure, different values: false
4. Symmetric Tree

Check if a binary tree is a mirror of itself (symmetric around its center).

★ Easy DFS Mirror Check
4

Problem Statement

A tree is symmetric if its left subtree is a mirror of its right subtree.

Approach

1
Create helper function to check if two subtrees are mirrors.
2
Compare root.left with root.right, matching left.left with right.right and left.right with right.left.
3
Check values match and recurse on mirror-swapped children.

Complete C# Solution

csharp 
// LeetCode 101
public class Solution {
    public bool IsSymmetric(TreeNode root) {
        return IsMirror(root, root);
    }

    private bool IsMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return IsMirror(left.left, right.right) && IsMirror(left.right, right.left);
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Must check all nodes; space is recursion depth.

Edge Cases

  • Null tree: symmetric (true)
  • Single node: symmetric (true)
  • Skewed tree: not symmetric (false)
5. Binary Tree Level Order Traversal

Return a list of lists containing node values at each level of the tree.

★★ Medium BFS Queue
5

Problem Statement

Given a binary tree, return its level-order traversal (BFS). Return a list of lists where each inner list contains nodes at that depth level.

Approach

1
Initialize a queue with the root node.
2
While queue is not empty, process all nodes at current level (use queue.Count as level size).
3
For each level, enqueue all children and add values to result list.

Complete C# Solution

csharp 
// LeetCode 102
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            var currentLevel = new List<int>();

            // Process all nodes at current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                currentLevel.Add(node.val);
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.Add(currentLevel);
        }
        return result;
    }
}

Complexity Analysis

Time
O(n)
Space
O(w)

w = max width (max nodes at any level); for complete binary tree w ≤ n/2.

Edge Cases

  • Null tree: empty result
  • Single node: one level
  • Skewed tree: each level has 1 node, w = 1
  • Complete binary tree: w = n/2 for bottom level
6. Validate Binary Search Tree

Check if a binary tree is a valid BST where all left values are smaller and right values are larger than parent.

★★ Medium DFS BST Property
6

Problem Statement

Validate a BST: for every node, all nodes in left subtree must be strictly less than the node's value, and all nodes in right subtree must be strictly greater.

Approach (Bounds Method)

1
Maintain min and max bounds for each node.
2
Check if node value is within [min, max) bounds; return false if not.
3
For left child, tighten upper bound to node.val; for right, tighten lower bound.

Complete C# Solution

csharp 
// LeetCode 98 - Bounds approach (avoids overflow)
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }

    private bool Validate(TreeNode node, long min, long max) {
        if (node == null) return true;

        // Check bounds
        if (node.val <= min || node.val >= max) return false;

        // Recursively validate subtrees with updated bounds
        return Validate(node.left, min, node.val) &&
               Validate(node.right, node.val, max);
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Note: Inorder traversal method also works: if inorder traversal is sorted, tree is BST.

Edge Cases

  • Single node: valid BST
  • Invalid subtle case: node.val = max int allowed in subtree range
  • Duplicate values: invalid BST (must be strictly less/greater)
7. Lowest Common Ancestor (BST)

Find the lowest common ancestor of two nodes in a binary search tree using BST properties.

★★ Medium DFS BST Property
7

Problem Statement

Given a BST and two node values p and q, find their LCA—the lowest node that is an ancestor of both.

Approach

1
Exploit BST property: if both p and q are less than node, LCA is in left subtree.
2
If both are greater, LCA is in right subtree.
3
Otherwise (one on each side or at current node), current node is the LCA.

Complete C# Solution

csharp 
// LeetCode 235
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;

        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                // Both in left subtree
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                // Both in right subtree
                current = current.right;
            } else {
                // One on each side or at current node
                return current;
            }
        }
        return current;
    }
}

Complexity Analysis

Time
O(log n) to O(n)
Space
O(1)

Balanced BST: O(log n); skewed: O(n). Space is constant (no recursion).

Edge Cases

  • p or q is the LCA itself: returns that node
  • Nodes at same level: LCA is a common parent
  • Deep skewed tree: O(n) time needed
8. Lowest Common Ancestor (Binary Tree)

Find LCA in an arbitrary binary tree (not necessarily a BST) using postorder DFS.

★★ Medium DFS Postorder
8

Problem Statement

Given a binary tree and two node values, find their LCA. The tree is not necessarily a BST.

Approach

1
Use postorder DFS: process left subtree, right subtree, then current node.
2
If node matches p or q, return it; if both subtrees return non-null, current is LCA.
3
Otherwise, return whichever subtree found a match (or null if neither).

Complete C# Solution

csharp 
// LeetCode 236
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        // Postorder: check subtrees first
        TreeNode left = LowestCommonAncestor(root.left, p, q);
        TreeNode right = LowestCommonAncestor(root.right, p, q);

        // If both found, current is LCA
        if (left != null && right != null) return root;

        // Return whichever subtree found a match
        return left ?? right;
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Must visit all nodes in worst case; postorder ensures correct LCA detection.

Edge Cases

  • p or q is the LCA: returns that node
  • Both in same subtree: LCA is that subtree root
  • Nodes in different subtrees: LCA is current node
9. Path Sum

Check if the tree has a root-to-leaf path whose sum equals a target value.

★ Easy DFS Path Accumulation
9

Problem Statement

Given a binary tree and target sum, return true if any root-to-leaf path sums to the target.

Approach

1
Use DFS, accumulating sum along the path from root.
2
At leaf nodes, check if accumulated sum equals target.
3
Return true if any path matches; false otherwise.

Complete C# Solution

csharp 
// LeetCode 112
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        return DFS(root, targetSum, 0);
    }

    private bool DFS(TreeNode node, int target, int sum) {
        if (node == null) return false;

        sum += node.val;

        // Leaf node check
        if (node.left == null && node.right == null) {
            return sum == target;
        }

        // Recurse on children
        return DFS(node.left, target, sum) || DFS(node.right, target, sum);
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Worst case: visit all nodes; best case: O(log n) if found early in balanced tree.

Edge Cases

  • Null tree: false
  • Single node: true if node.val == target
  • Negative numbers: sums can decrease
10. Path Sum III

Count all paths in a tree (not necessarily root-to-leaf) that sum to a target value.

★★ Medium DFS Prefix Sum
10

Problem Statement

Count the number of paths in a binary tree that sum to a target. Paths can start and end at any node (not necessarily root-to-leaf).

Approach

1
Use prefix sum map: for each node, compute path sum from some ancestor to this node.
2
If (current_sum - target) exists in map, there's a path ending at current node with sum = target.
3
Track prefix sums in a map, backtrack to clean up after exploring subtrees.

Complete C# Solution

csharp 
// LeetCode 437
public class Solution {
    public int PathSum(TreeNode root, int targetSum) {
        var prefixSums = new Dictionary<long, int>();
        prefixSums[0] = 1; // Base case: empty path
        return DFS(root, 0, targetSum, prefixSums);
    }

    private int DFS(TreeNode node, long pathSum, int target,
                    Dictionary<long, int> prefixSums) {
        if (node == null) return 0;

        // Add current node to path sum
        pathSum += node.val;

        // Count paths ending at this node
        int count = 0;
        if (prefixSums.ContainsKey(pathSum - target)) {
            count = prefixSums[pathSum - target];
        }

        // Add current path sum to map
        if (!prefixSums.ContainsKey(pathSum)) {
            prefixSums[pathSum] = 0;
        }
        prefixSums[pathSum]++;

        // Recurse on children
        count += DFS(node.left, pathSum, target, prefixSums);
        count += DFS(node.right, pathSum, target, prefixSums);

        // Backtrack: remove path sum
        prefixSums[pathSum]--;
        if (prefixSums[pathSum] == 0) {
            prefixSums.Remove(pathSum);
        }

        return count;
    }
}

Complexity Analysis

Time
O(n)
Space
O(h)

Prefix sum approach eliminates nested loops; map stores at most h entries (path length).

Edge Cases

  • Target = 0: must account for zero-sum paths
  • Negative values: prefix sum approach handles them
  • Multiple paths with same sum: count all
11. Kth Smallest Element in BST

Find the kth smallest element in a BST using inorder traversal.

★★ Medium Inorder BST Property
11

Problem Statement

Given a BST, return the kth smallest element (1-indexed). Inorder traversal yields sorted values.

Approach

1
Use inorder traversal (Left → Root → Right) which yields BST values in sorted order.
2
Count nodes visited; when count reaches k, return the current node's value.
3
Use a helper class or ref variable to track count across recursive calls.

Complete C# Solution

csharp 
// LeetCode 230
public class Solution {
    private int count = 0;
    private int result = 0;

    public int KthSmallest(TreeNode root, int k) {
        count = 0;
        Inorder(root, k);
        return result;
    }

    private void Inorder(TreeNode node, int k) {
        if (node == null) return;

        // Visit left subtree
        Inorder(node.left, k);

        // Process current node
        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        // Visit right subtree
        Inorder(node.right, k);
    }
}

Complexity Analysis

Time
O(k) to O(n)
Space
O(h)

Best case: O(k) if kth element is found early; worst: O(n) if k = n.

Edge Cases

  • k = 1: returns minimum element (leftmost node)
  • k = n: returns maximum element (rightmost node)
  • Balanced vs. skewed: affects recursion depth but not overall time
12. Serialize and Deserialize Binary Tree

Convert a binary tree to a string representation and back, preserving structure and values.

★★★ Hard Preorder DFS BFS Queue
12

Problem Statement

Serialize a binary tree to a string and deserialize back to the original tree. Preserve structure using markers for null children.

Approach (Preorder DFS)

1
Serialize using preorder (Root → Left → Right) with "null" markers for empty nodes.
2
Deserialize by consuming tokens in preorder order; reconstruct recursively.
3
Use comma-separated format for clarity; null values signal stopping recursion.

Complete C# Solution

csharp 
// LeetCode 297
public class Codec {
    // Encodes tree to string (preorder DFS)
    public string serialize(TreeNode root) {
        var sb = new StringBuilder();
        SerializeDFS(root, sb);
        return sb.ToString();
    }

    private void SerializeDFS(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.Append("null,");
            return;
        }
        sb.Append(node.val).Append(",");
        SerializeDFS(node.left, sb);
        SerializeDFS(node.right, sb);
    }

    // Decodes string to tree (preorder reconstruction)
    public TreeNode deserialize(string data) {
        var tokens = new Queue<string>(data.Split(','));
        return DeserializeDFS(tokens);
    }

    private TreeNode DeserializeDFS(Queue<string> tokens) {
        string val = tokens.Dequeue();
        if (val == "null") return null;

        TreeNode node = new TreeNode(int.Parse(val));
        node.left = DeserializeDFS(tokens);
        node.right = DeserializeDFS(tokens);
        return node;
    }
}

Complexity Analysis

Time
O(n)
Space
O(n)

Both serialize and deserialize: visit all n nodes; space for string representation is O(n).

Edge Cases

  • Null tree: serializes to "null"
  • Single node: serializes to "val,null,null"
  • Duplicate values: handled correctly; structure preserved
  • Very deep tree: string may be large but deserializes correctly
Summary

Key Takeaways

Mastering tree problems requires understanding traversal patterns, BST properties, and problem-solving strategies:

💡
Traversal choice matters: DFS (inorder, preorder, postorder) for ancestors and path problems; BFS for level-order and distance problems.
💡
BST optimization: Exploit the left < root < right property to avoid full tree scans in problems 6 and 7.
💡
Path problems: Accumulate state (sum, prefix map) along the path; postorder DFS works for checking ancestor relationships.
💡
Serialization pattern: Use preorder + null markers to uniquely encode tree structure; queue-based deserialization reconstructs efficiently.

Recommended Practice Order

  1. Problems 1-4: Start with easy DFS traversal problems to build comfort with recursion.
  2. Problem 5: BFS/level-order introduces queue-based tree processing.
  3. Problems 6-7: BST-specific optimizations show importance of tree properties.
  4. Problems 8-10: Advanced DFS patterns (LCA, path sums) combine multiple concepts.
  5. Problems 11-12: Capstone problems integrating traversal, state tracking, and serialization.