Trees Basics

1. Introduction: The Branching Hierarchy

Arrays, Linked Lists, Stacks, and Queues are Linear data structures. There is a strict sequence: element A comes before element B. But real-world data is rarely linear. A company org chart has a CEO at the top, managing VPs, who manage Directors. Your computer's file system has a Root folder (C:\), which contains subfolders, which contain files.

This hierarchical data is modeled using a Tree. In computer science, a Tree is an undirected graph with no cycles, where every node has exactly one parent (except the very top node). Trees are the foundation of database indexing, routing algorithms, and AI decision-making.

2. Core Concept: Tree Terminology

To talk about trees, you must know the vocabulary:

• Node: A single data unit containing a value and pointers to other nodes.
• Root: The absolute top node of the tree. It has no parent.
• Edge: The connection between a parent and a child.
• Leaf: A node with NO children. (The bottom of the tree).
• Parent / Child / Sibling: A node is a parent if it points to children. Siblings share the exact same parent.
• Depth: The number of edges from the Root down to a specific node. (Root is Depth 0).
• Height: The number of edges from a specific node down to the deepest Leaf. (Leaves are Height 0).

The Binary Tree

A general tree can have infinite children per node (e.g., a folder can have 100 files). However, 95% of algorithmic interview questions focus strictly on the Binary Tree. In a Binary Tree, every node is restricted to a maximum of two children, strictly labeled as the left child and the right child.

3. Beginner Code Example: Defining and Building a Binary Tree

Unlike an Array which is built into Java (int[]), a Binary Tree must be constructed manually using a custom Class.

The Insight: A TreeNode is almost exactly the same as a Linked List ListNode, but instead of a single next pointer, it branches into two.

// The universal LeetCode definition for a Binary Tree Node
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    // Constructors
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class TreeBuilder {
    public static void main(String[] args) {
        // Constructing a tree manually:
        //       1
        //      / \
        //     2   3
        //    /
        //   4
        
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        
        // Is node 4 a leaf? Yes, its left and right are null by default!
        System.out.println(root.left.left.left == null); // true
    }
}

4. Intermediate Code Example: Invert a Binary Tree

Problem Statement: (LeetCode 226) Given the root of a binary tree, invert the tree, and return its root. (This is the infamous problem that supposedly caused the creator of Homebrew to be rejected by Google).

Inverting a tree means creating a perfect mirror image. The left child becomes the right child, and vice versa, for every single node in the tree.

The Insight: This is solved using basic Recursion. For any given node, we simply swap its left and right pointers. Then, we recursively tell the left child to invert itself, and tell the right child to invert itself!

public class InvertTree {
    public TreeNode invertTree(TreeNode root) {
        // Base Case: If the node is null, there is nothing to invert!
        if (root == null) {
            return null;
        }
        
        // 1. Swap the left and right pointers of the CURRENT node
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // 2. Recursively invert the subtrees
        // (Note: root.left used to be the right subtree, but we just swapped it! 
        // It doesn't matter, we still need to invert both sides).
        invertTree(root.left);
        invertTree(root.right);
        
        // 3. Return the modified root
        return root;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ because we visit every single node exactly once to perform the swap.
• Space Complexity: $O(H)$ where $H$ is the height of the tree. In the worst case (a completely unbalanced line), this is $O(N)$. In a perfectly balanced tree, it is $O(\log N)$.

5. Concept: Array Representation of Binary Trees

If a Binary Tree is perfectly Complete (every level is completely filled, except maybe the last one which is filled left-to-right), we don't actually need the TreeNode class!

We can store the tree in a flat int[] array. (This is exactly how Heaps are implemented).

• The Root is at index 0.
• The Left Child of index i is at index 2 * i + 1.
• The Right Child of index i is at index 2 * i + 2.
• The Parent of index i is at index (i - 1) / 2.

Why don't we use this for all trees? If the tree is highly unbalanced (e.g., node 0 has a right child, which has a right child, which has a right child), the array would be 99% empty space, wasting massive amounts of memory. Pointer-based TreeNodes are memory-efficient for sparse/unbalanced trees.

6. Common Mistakes Beginners Make

1. NullPointerExceptions on Leaves

   • The Mistake: Writing if (root.left == null) without first checking if (root == null).
   • Why it's wrong: If root itself is null, attempting to access .left throws an exception and crashes your code.
   • The Fix: The very first line of almost every recursive tree function should be if (root == null) return ...;.

2. Losing the Root Reference

   • The Mistake: while(root != null) { root = root.left; }
   • Why it's wrong: If you reassign the root variable to point to a child, you permanently lose the reference to the actual top of the tree. If you need to traverse iteratively, always create a temporary pointer: TreeNode curr = root;.

3. Thinking Trees can have Cycles

   • The Mistake: Trying to use a HashSet to track visited nodes in a standard Binary Tree.
   • Why it's wrong: By strict mathematical definition, a Tree has no cycles and no converging paths. A node can only be reached via one exact path from the root. Tracking visited nodes wastes memory. (Note: If the problem states it's a "Graph", cycles might exist).

7. Interview Q&A

Q1: What is a Binary Search Tree (BST)? Answer: A BST is a Binary Tree with a strict mathematical rule: For any given node, ALL values in its left subtree must be strictly smaller than the node's value, and ALL values in its right subtree must be strictly larger. This property allows $O(\log N)$ search times.

Q2: What is the difference between a Full, Complete, and Perfect Binary tree? Answer:

• Full: Every node has exactly 0 or 2 children. (No single parents).
• Complete: All levels are completely filled except possibly the last level, which is filled strictly from left to right.
• Perfect: All interior nodes have 2 children, and all leaves are at the exact same depth. (Perfectly symmetrical).

8. Practice Problems

1. Invert Binary Tree (LeetCode 226)
   • Goal: Master the basic recursive swap.
2. Merge Two Binary Trees (LeetCode 617)
   • Hint: Traverse both trees simultaneously. If one is null, return the other!
3. Same Tree (LeetCode 100)
   • Hint: Are the values equal? Are the left subtrees the same? Are the right subtrees the same?

9. Summary

• Hierarchy: Trees represent parent-child relationships without cycles.
• Binary Trees: Maximum of 2 children per node (left, right).
• The Code: class TreeNode { int val; TreeNode left; TreeNode right; }.
• Recursion: Trees are fundamentally recursive data structures. If you can solve a problem for a 3-node tree, that same logic automatically solves a 3-million node tree.

Advanced Code Implementations

// Example: Binary Tree Level Order Traversal (BFS)
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class LevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                level.add(curr.val);
                if (curr.left != null) q.offer(curr.left);
                if (curr.right != null) q.offer(curr.right);
            }
            res.add(level);
        }
        return res;
    }
}

// Example: Lowest Common Ancestor of a Binary Tree (DFS)
public class LCA {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null, or matches one of the target nodes
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // Traverse left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // If both left and right return a node, root is the LCA
        if (left != null && right != null) {
            return root;
        }
        
        // Otherwise return the non-null child
        return left != null ? left : right;
    }
}

Expanded Interview Q&A

Q1: What is the difference between a Binary Tree and a Binary Search Tree (BST)?

Answer: A Binary Tree has at most two children per node. A BST adds the property that left children are strictly smaller and right children are strictly greater than their parent.

Q2: What are the three types of Depth First Search for trees?

Answer: Pre-order (Root-Left-Right), In-order (Left-Root-Right), and Post-order (Left-Right-Root).

Q3: What is the time and space complexity of Level Order Traversal?

Answer: Time complexity is O(N) where N is number of nodes. Space complexity is O(N) as the queue will at most hold N/2 nodes (at the bottom level).

Q4: What is a balanced binary tree?

Answer: A tree where the heights of the two child subtrees of any node differ by at most one (e.g., AVL tree, Red-Black tree).

Q5: How do you serialize and deserialize a binary tree?

Answer: Use Pre-order or Level-order traversal, explicitly storing null nodes as a special character (like '#') to reconstruct the exact structure later.