Trees & Tries

advanced5 problems· Prerequisites: Big O & Complexity, Arrays & Strings, Recursion & Backtracking

Tree Basics

A tree is a hierarchical structure with a root node and children nodes. Each node has a value and pointers to its children.

Binary Tree: Each node has at most 2 children (left and right). Binary Search Tree (BST): For every node: left < node < right.

Operation	BST (balanced)	BST (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traverse	O(n)	O(n)

Problem

Visit every node of this binary search tree in a specific traversal order.

Tree TraversalStep 1 / 8

Visiting 5

Speed:

Unvisited Current VisitedInorder: left → root → right

TreeNode class and traversalsC#

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;
    }
}

// DFS Traversals (recursive)
void Inorder(TreeNode node) {      // left → root → right
    if (node == null) return;
    Inorder(node.left);
    Console.Write(node.val + " ");
    Inorder(node.right);
}

void Preorder(TreeNode node) {     // root → left → right
    if (node == null) return;
    Console.Write(node.val + " ");
    Preorder(node.left);
    Preorder(node.right);
}

void Postorder(TreeNode node) {    // left → right → root
    if (node == null) return;
    Postorder(node.left);
    Postorder(node.right);
    Console.Write(node.val + " ");
}

// BFS (Level order)
void LevelOrder(TreeNode root) {
    var q = new Queue<TreeNode>();
    q.Enqueue(root);
    while (q.Count > 0) {
        var node = q.Dequeue();
        Console.Write(node.val + " ");
        if (node.left != null) q.Enqueue(node.left);
        if (node.right != null) q.Enqueue(node.right);
    }
}

BST Operations

BST property: left.val < node.val < right.val for ALL nodes (not just immediate children).

This property enables fast search - at each node you eliminate half the tree.

BST search, insert, validateC#

// BST Search - O(log n) average
TreeNode Search(TreeNode root, int target) {
    while (root != null) {
        if (root.val == target) return root;
        root = target < root.val ? root.left : root.right;
    }
    return null;
}

// BST Insert - O(log n)
TreeNode Insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = Insert(root.left, val);
    else root.right = Insert(root.right, val);
    return root;
}

// Validate BST - O(n)
bool IsValidBST(TreeNode root) {
    return Validate(root, long.MinValue, long.MaxValue);
}

bool Validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return Validate(node.left, min, node.val)
        && Validate(node.right, node.val, max);
}

Trie (Prefix Tree)

A trie (prefix tree) stores strings in a tree where each node represents a character. Used for autocomplete, spell check, and IP routing.

Operation	Trie
Insert	O(m) where m = word length
Search	O(m)
Prefix search	O(m)

Space: O(total characters across all words).

Trie implementationC#

public class TrieNode {
    public Dictionary<char, TrieNode> children = new();
    public bool isEnd = false;
}

public class Trie {
    private readonly TrieNode root = new();

    public void Insert(string word) {
        var node = root;
        foreach (char c in word) {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isEnd = true;
    }

    public bool Search(string word) {
        var node = Find(word);
        return node != null && node.isEnd;
    }

    public bool StartsWith(string prefix) {
        return Find(prefix) != null;
    }

    private TrieNode Find(string s) {
        var node = root;
        foreach (char c in s) {
            if (!node.children.TryGetValue(c, out node))
                return null;
        }
        return node;
    }
}

When to Use Trees & Tries

Trees are the right choice when:

Data has a hierarchical structure (filesystem, DOM, org chart)
You need fast search with ordering (BST: O(log n) average)
You need range queries (BST: find all values between x and y)
Data naturally branches (decision trees, game trees)

Trees vs other structures:

Structure	Use when
Array / List	Flat, ordered data with index access
Hash map	Key-value lookup (no ordering needed)
Tree	Hierarchical OR needs sorted order OR range queries
Graph	No hierarchy, arbitrary connections

When NOT to use a tree:

Data is flat (just use an array)
You only need exact membership lookup (use a hash set)
The tree would be unbalanced (use a balanced tree library)

Trie vs Hash Set for strings:

Criterion	Trie	Hash Set
Prefix search	O(m) - fast	O(n * L) - must scan all
Memory	More (node overhead)	Less
Exact membership	O(m)	O(1) average
Use case	Autocomplete, spell check	Simple word lookup

Decision guide:

Signal	Structure
"Sorted order of keys"	BST
"Find all values in range"	BST
"Hierarchy / parent-child"	Tree
"Autocomplete / prefix search"	Trie
"Fast lookup, no order needed"	Hash set/map
"Relationships between items"	Graph

Common Mistakes / Gotchas

BST validation: checking only immediate children A common mistake: left.val < node.val < right.val. This is WRONG. ALL nodes in the left subtree must be < node.val. Example: root=5, left=3, left.right=6 would pass the naive check but violates BST (6 > 5). Use the min/max range approach.

Forgetting null checks on tree nodes node.left and node.right can be null. Always check if (node == null) return before accessing children.

Recursion depth in skewed trees A tree with n nodes can be n levels deep if it's skewed (basically a linked list). Recursive traversal uses O(n) stack space and risks overflow. Consider iterative traversal for worst-case trees.

Confusing tree, BST, and trie

Tree: generic hierarchical structure (any order)
BST: ordered binary tree (left < node < right)
Trie: prefix tree for strings (each node = one character)

Trie: forgetting the end-of-word marker Without isEnd flag, search("app") returns true even if only "apple" was inserted. The flag distinguishes prefix from complete word.

Common Interview Patterns

Tree traversal - inorder (sorted BST), preorder (serialization), level order (BFS)
LCA (Lowest Common Ancestor) - recursive or iterative for BST
Diameter / max path sum - post-order traversal with global variable
Serialize / deserialize - preorder with null markers
Trie problems - autocomplete, word search, word break
Balanced tree check - compute height and check balance at each node

Forgetting null checks on tree nodes node.left and node.right can be null. Always check if (node == null) return before accessing children.

Confusing tree, BST, and trie

Tree: generic hierarchical structure (any order)
BST: ordered binary tree (left < node < right)
Trie: prefix tree for strings (each node = one character)

Trie: forgetting the end-of-word marker Without isEnd flag, search("app") returns true even if only "apple" was inserted. The flag distinguishes prefix from complete word.