Home/Data Structures/Trees

Trees

🎯 Explain Like I'm 5...

Imagine your family tree! At the top, there's your grandpa (the root). Below him are his children (your parents), and below them are their children (you and your siblings)!

🌳 Trees - Like a Family Tree:

  • • Grandpa (Root): The person at the very top - everyone comes from him!
  • • Parents (Nodes): Grandpa's children - they connect grandpa to you!
  • • You & Siblings (Leaves): The youngest generation - no children yet!

Each person can only have ONE parent (except grandpa who has none), but can have MANY children! 👨‍👩‍👧‍👦

🎄 Binary Trees - Maximum 2 Children:

In a binary tree, each person can have at most 2 children (left child and right child). Like if everyone in your family had only 0, 1, or 2 kids!

  • • Left Child: The first kid
  • • Right Child: The second kid
  • • Leaf: Someone with no kids (like you!)

🚀 Why Are Trees Useful?

  • • Trees help organize data in a hierarchy - like a company org chart!
  • • Binary Search Trees let you find things super fast - like a phone book!
  • • Trees are used everywhere: file systems, databases, HTML pages, and more!

🔧 Basic Operations

Creating a Tree Node

TreeNode.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Basic TreeNode class - the building block of trees!
public class TreeNode {
    int val;           // The value stored in this node
    TreeNode left;     // Pointer to left child
    TreeNode right;    // Pointer to right child
    // Constructor - creates a new node
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
// Example: Building a simple tree
public class TreeExample {
    public static void main(String[] args) {
        // Create root node (grandpa!)
        TreeNode root = new TreeNode(10);
        // Add left and right children (parents!)
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        // Add grandchildren (you and siblings!)
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(12);
        root.right.right = new TreeNode(18);
        /*
        Tree structure:
                10
               /  \
              5    15
             / \   / \
            3   7 12  18
        */
        System.out.println("Root value: " + root.val);           // 10
        System.out.println("Left child: " + root.left.val);      // 5
        System.out.println("Right child: " + root.right.val);    // 15
    }
}

Tree Traversals

Inorder Traversal (Left → Root → Right)

InorderTraversal.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class InorderTraversal {
    // Inorder: Visit left subtree, then root, then right subtree
    // For BST, this gives you nodes in SORTED order!
    public static void inorder(TreeNode root) {
        if (root == null) {
            return;  // Base case: empty tree
        }
        inorder(root.left);              // Visit left subtree first
        System.out.print(root.val + " "); // Then visit root
        inorder(root.right);             // Finally visit right subtree
    }
    public static void main(String[] args) {
        // Build tree:    4
        //               / \
        //              2   6
        //             / \ / \
        //            1  3 5  7
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.print("Inorder: ");
        inorder(root);  // Output: 1 2 3 4 5 6 7 (sorted!)
    }
}

Preorder Traversal (Root → Left → Right)

PreorderTraversal.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class PreorderTraversal {
    // Preorder: Visit root first, then left subtree, then right subtree
    // Useful for creating a copy of the tree or prefix notation
    public static void preorder(TreeNode root) {
        if (root == null) {
            return;  // Base case: empty tree
        }
        System.out.print(root.val + " "); // Visit root first
        preorder(root.left);              // Then visit left subtree
        preorder(root.right);             // Finally visit right subtree
    }
    public static void main(String[] args) {
        // Build tree:    4
        //               / \
        //              2   6
        //             / \ / \
        //            1  3 5  7
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.print("Preorder: ");
        preorder(root);  // Output: 4 2 1 3 6 5 7
    }
}

Postorder Traversal (Left → Right → Root)

PostorderTraversal.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class PostorderTraversal {
    // Postorder: Visit left subtree, then right subtree, then root
    // Useful for deleting tree or postfix notation
    public static void postorder(TreeNode root) {
        if (root == null) {
            return;  // Base case: empty tree
        }
        postorder(root.left);             // Visit left subtree first
        postorder(root.right);            // Then visit right subtree
        System.out.print(root.val + " "); // Finally visit root
    }
    public static void main(String[] args) {
        // Build tree:    4
        //               / \
        //              2   6
        //             / \ / \
        //            1  3 5  7
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.print("Postorder: ");
        postorder(root);  // Output: 1 3 2 5 7 6 4
    }
}

Common Tree Operations

Insert Node in BST

BSTInsert.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class BSTInsert {
    // Insert a node into Binary Search Tree
    // BST property: left < root < right
    public static TreeNode insert(TreeNode root, int val) {
        // If tree is empty, create new node
        if (root == null) {
            return new TreeNode(val);
        }
        // Decide whether to go left or right
        if (val < root.val) {
            // Value is smaller, go left
            root.left = insert(root.left, val);
        } else if (val > root.val) {
            // Value is larger, go right
            root.right = insert(root.right, val);
        }
        // If val == root.val, don't insert duplicate
        return root;
    }
    public static void main(String[] args) {
        TreeNode root = null;
        // Insert values
        root = insert(root, 10);
        root = insert(root, 5);
        root = insert(root, 15);
        root = insert(root, 3);
        root = insert(root, 7);
        /*
        Resulting BST:
              10
             /  \
            5    15
           / \
          3   7
        */
        // Print inorder to verify (should be sorted)
        System.out.print("Inorder: ");
        inorder(root);  // Output: 3 5 7 10 15
    }
    // Helper function for printing
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

Search in BST

BSTSearch.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class BSTSearch {
    // Search for a value in Binary Search Tree
    // Returns true if found, false otherwise
    // Time complexity: O(log n) for balanced tree, O(n) worst case
    public static boolean search(TreeNode root, int target) {
        // Base case: empty tree or not found
        if (root == null) {
            return false;
        }
        // Found the target!
        if (root.val == target) {
            return true;
        }
        // Target is smaller, search left subtree
        if (target < root.val) {
            return search(root.left, target);
        }
        // Target is larger, search right subtree
        return search(root.right, target);
    }
    // Alternative: return the node instead of boolean
    public static TreeNode searchNode(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (target < root.val) {
            return searchNode(root.left, target);
        }
        return searchNode(root.right, target);
    }
    public static void main(String[] args) {
        // Build BST:    10
        //              /  \
        //             5    15
        //            / \   / \
        //           3   7 12  18
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(12);
        root.right.right = new TreeNode(18);
        System.out.println("Search 7: " + search(root, 7));    // true
        System.out.println("Search 12: " + search(root, 12));  // true
        System.out.println("Search 20: " + search(root, 20));  // false
        System.out.println("Search 1: " + search(root, 1));    // false
    }
}

Calculate Tree Height

TreeHeight.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class TreeHeight {
    // Calculate the height of a tree
    // Height = number of edges on longest path from root to leaf
    // Empty tree has height -1, single node has height 0
    public static int height(TreeNode root) {
        // Base case: empty tree
        if (root == null) {
            return -1;
        }
        // Calculate height of left and right subtrees
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        // Height is 1 + max of left and right heights
        return 1 + Math.max(leftHeight, rightHeight);
    }
    // Alternative: counting nodes instead of edges
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }
    public static void main(String[] args) {
        // Build tree:    1
        //               / \
        //              2   3
        //             / \
        //            4   5
        //           /
        //          6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.left.left = new TreeNode(6);
        System.out.println("Height: " + height(root));        // 3
        System.out.println("Max Depth: " + maxDepth(root));   // 4
        // Single node tree
        TreeNode single = new TreeNode(10);
        System.out.println("Single node height: " + height(single));  // 0
    }
}

💡 Common Problems & Solutions

Problem 1: Maximum Depth of Binary Tree

Find how many levels deep the tree goes - like counting generations in your family!

💡 How it works (Recursive Height Calculation):

The Challenge: Find the maximum depth (number of levels) from root to deepest leaf

The Recursive Solution:

1. Base case: Empty tree has depth 0

2. Recursive case:

• Find depth of left subtree

• Find depth of right subtree

• Return 1 + max(left depth, right depth)

Why does this work?

The depth of a tree is 1 (current node) plus the maximum depth of its subtrees!

Visual Example:

Tree: 3
/ \
9 20
/ \
15 7

Step 1: maxDepth(3) calls:
- maxDepth(9) → returns 1 (leaf node)
- maxDepth(20) calls:
- maxDepth(15) → returns 1
- maxDepth(7) → returns 1
- returns 1 + max(1,1) = 2
- returns 1 + max(1,2) = 3 ✅

Result: Maximum depth = 3

⏱️ Time Complexity: O(n) - visit every node once

💾 Space Complexity: O(h) - recursion stack height

MaxDepth.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class MaxDepth {
    // Find the maximum depth (height) of a binary tree
    // Depth is the number of nodes from root to deepest leaf
    // Time: O(n) - visit every node once
    // Space: O(h) - recursion stack where h is height
    public static int maxDepth(TreeNode root) {
        // Base case: empty tree has depth 0
        if (root == null) {
            return 0;
        }
        // Recursively find depth of left and right subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        // Current depth is 1 + max of subtree depths
        return 1 + Math.max(leftDepth, rightDepth);
    }
    public static void main(String[] args) {
        // Build tree:    3
        //               / \
        //              9   20
        //                 /  \
        //                15   7
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println("Max depth: " + maxDepth(root));  // 3
        // Unbalanced tree
        TreeNode unbalanced = new TreeNode(1);
        unbalanced.left = new TreeNode(2);
        unbalanced.left.left = new TreeNode(3);
        unbalanced.left.left.left = new TreeNode(4);
        System.out.println("Unbalanced depth: " + maxDepth(unbalanced));  // 4
    }
}

Problem 2: Validate Binary Search Tree

Check if a tree follows BST rules: left < root < right at every node!

💡 How it works (Range Validation):

The Challenge: Verify BST property: ALL left descendants < node < ALL right descendants

Common Mistake: Only checking immediate children is NOT enough!

The Correct Solution (Track Min/Max Range):

1. Each node must be within a valid range [min, max]

2. For left child: Range becomes [min, parent.val]

3. For right child: Range becomes [parent.val, max]

4. Recursively validate all nodes

Visual Example:

Valid BST: 5 Range: [-∞, +∞]
/ \
3 7
/ \
2 4

Check node 5: -∞ < 5 < +∞ ✅
Check node 3: -∞ < 3 < 5 ✅ (left child range: [-∞, 5])
Check node 7: 5 < 7 < +∞ ✅ (right child range: [5, +∞])
Check node 2: -∞ < 2 < 3 ✅
Check node 4: 3 < 4 < 5 ✅

Invalid BST: 5
/ \
1 4
/ \
3 6

Check node 5: -∞ < 5 < +∞ ✅
Check node 4: 5 < 4 < +∞ ❌ (4 is NOT > 5!)
Invalid BST!

⏱️ Time Complexity: O(n) - visit every node once

💾 Space Complexity: O(h) - recursion stack height

ValidateBST.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class ValidateBST {
    // Check if a binary tree is a valid Binary Search Tree
    // BST property: ALL left descendants < node < ALL right descendants
    // Time: O(n), Space: O(h) for recursion
    public static boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    // Helper function with min and max constraints
    private static boolean validate(TreeNode node, long min, long max) {
        // Empty tree is valid BST
        if (node == null) {
            return true;
        }
        // Current node must be within min and max range
        if (node.val <= min || node.val >= max) {
            return false;
        }
        // Left subtree: all values must be < node.val
        // Right subtree: all values must be > node.val
        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
    public static void main(String[] args) {
        // Valid BST:    5
        //              / \
        //             3   7
        //            / \
        //           2   4
        TreeNode valid = new TreeNode(5);
        valid.left = new TreeNode(3);
        valid.right = new TreeNode(7);
        valid.left.left = new TreeNode(2);
        valid.left.right = new TreeNode(4);
        System.out.println("Valid BST: " + isValidBST(valid));  // true
        // Invalid BST:  5
        //              / \
        //             1   4
        //                / \
        //               3   6  <- 6 > 5, violates BST!
        TreeNode invalid = new TreeNode(5);
        invalid.left = new TreeNode(1);
        invalid.right = new TreeNode(4);
        invalid.right.left = new TreeNode(3);
        invalid.right.right = new TreeNode(6);
        System.out.println("Invalid BST: " + isValidBST(invalid));  // false
    }
}

Problem 3: Lowest Common Ancestor

Find the closest shared ancestor of two nodes - like finding your common grandparent!

💡 How it works (BST Split Point):

The Challenge: Find the lowest (deepest) common ancestor of two nodes

Key Idea for BST: LCA is the split point where paths to both nodes diverge!

The Solution:

1. If both nodes are smaller than current: Go left (both are in left subtree)

2. If both nodes are larger than current: Go right (both are in right subtree)

3. Otherwise: Current node is the LCA! (nodes are on different sides)

Visual Example:

BST: 6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5

Find LCA of nodes 2 and 8:
Current = 6
2 < 6 and 8 > 6 → Different sides!
LCA = 6 ✅

Find LCA of nodes 2 and 4:
Current = 6
2 < 6 and 4 < 6 → Both in left subtree
Go left → Current = 2
2 == 2 and 4 > 2 → Different sides!
LCA = 2 ✅

Find LCA of nodes 3 and 5:
Start at 6 → go left to 2 → go right to 4
3 < 4 and 5 > 4 → Different sides!
LCA = 4 ✅

⏱️ Time Complexity: O(h) - height of tree for BST

💾 Space Complexity: O(1) - iterative solution

LowestCommonAncestor.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class LowestCommonAncestor {
    // Find lowest common ancestor (LCA) in a Binary Search Tree
    // LCA is the lowest node that has both p and q as descendants
    // Time: O(h) where h is height, Space: O(1) iterative
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Start from root
        TreeNode current = root;
        while (current != null) {
            // Both nodes are in left subtree
            if (p.val < current.val && q.val < current.val) {
                current = current.left;
            }
            // Both nodes are in right subtree
            else if (p.val > current.val && q.val > current.val) {
                current = current.right;
            }
            // We found the split point! This is the LCA
            else {
                return current;
            }
        }
        return null;
    }
    // Recursive version for general binary tree (not just BST)
    public static TreeNode lowestCommonAncestorGeneral(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestorGeneral(root.left, p, q);
        TreeNode right = lowestCommonAncestorGeneral(root.right, p, q);
        // If both left and right are not null, root is LCA
        if (left != null && right != null) {
            return root;
        }
        // Otherwise return non-null side
        return left != null ? left : right;
    }
    public static void main(String[] args) {
        // Build BST:    6
        //              / \
        //             2   8
        //            / \ / \
        //           0  4 7  9
        //             / \
        //            3   5
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        TreeNode p = root.left;          // Node 2
        TreeNode q = root.right;         // Node 8
        TreeNode lca = lowestCommonAncestor(root, p, q);
        System.out.println("LCA of 2 and 8: " + lca.val);  // 6
        p = root.left;                   // Node 2
        q = root.left.right;             // Node 4
        lca = lowestCommonAncestor(root, p, q);
        System.out.println("LCA of 2 and 4: " + lca.val);  // 2
    }
}

Problem 4: Count Total Nodes

Count how many nodes are in the tree - like counting all family members!

💡 How it works (Recursive Counting):

The Challenge: Count all nodes in the tree

The Recursive Solution:

1. Base case: Empty tree has 0 nodes

2. Recursive case:

• Count nodes in left subtree

• Count nodes in right subtree

• Return 1 (current node) + left count + right count

Pattern Recognition: This is a classic post-order traversal pattern!

Visual Example:

Tree: 1
/ \
2 3
/ \ \
4 5 6

countNodes(1) calls:
├─ countNodes(2) calls:
│ ├─ countNodes(4) → returns 1
│ ├─ countNodes(5) → returns 1
│ └─ returns 1 + 1 + 1 = 3
├─ countNodes(3) calls:
│ ├─ countNodes(null) → returns 0
│ ├─ countNodes(6) → returns 1
│ └─ returns 1 + 0 + 1 = 2
└─ returns 1 + 3 + 2 = 6 ✅

Total nodes = 6

⏱️ Time Complexity: O(n) - visit every node once

💾 Space Complexity: O(h) - recursion stack height

CountNodes.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class CountNodes {
    // Count the total number of nodes in a binary tree
    // Time: O(n) - must visit every node
    // Space: O(h) - recursion stack
    public static int countNodes(TreeNode root) {
        // Base case: empty tree has 0 nodes
        if (root == null) {
            return 0;
        }
        // Count this node + nodes in left subtree + nodes in right subtree
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    // Count leaf nodes (nodes with no children)
    public static int countLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // If node has no children, it's a leaf
        if (root.left == null && root.right == null) {
            return 1;
        }
        // Otherwise count leaves in subtrees
        return countLeaves(root.left) + countLeaves(root.right);
    }
    // Count nodes at a specific level
    public static int countNodesAtLevel(TreeNode root, int level) {
        if (root == null) {
            return 0;
        }
        if (level == 0) {
            return 1;  // We're at the target level
        }
        // Go down one level in both subtrees
        return countNodesAtLevel(root.left, level - 1) +
               countNodesAtLevel(root.right, level - 1);
    }
    public static void main(String[] args) {
        // Build tree:    1
        //               / \
        //              2   3
        //             / \   \
        //            4   5   6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        System.out.println("Total nodes: " + countNodes(root));      // 6
        System.out.println("Leaf nodes: " + countLeaves(root));      // 3
        System.out.println("Nodes at level 0: " + countNodesAtLevel(root, 0));  // 1
        System.out.println("Nodes at level 1: " + countNodesAtLevel(root, 1));  // 2
        System.out.println("Nodes at level 2: " + countNodesAtLevel(root, 2));  // 3
    }
}

🔑 Key Points to Remember

  • 1️⃣Trees are hierarchical - each node (except root) has exactly one parent
  • 2️⃣Binary trees have at most 2 children per node (left and right)
  • 3️⃣BST property: left subtree < node < right subtree (enables O(log n) search!)
  • 4️⃣Balanced trees have O(log n) operations, unbalanced can be O(n)
  • 5️⃣Three main traversals: inorder, preorder, postorder - each useful for different tasks

💪 Practice Problems

  • • Invert/mirror a binary tree
  • • Check if tree is balanced
  • • Binary tree level order traversal
  • • Serialize and deserialize binary tree
  • • Kth smallest element in BST
  • • Path sum problems
  • • Construct tree from preorder and inorder