Tree Basics

Photo by Emile Perron on Unsplash

🌳 What is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. Each node contains a value and references to its children.

Key Terminology

• Node: Individual element in the tree
• Root: Topmost node (no parent)
• Parent: Node that has children
• Child: Node that has a parent
• Leaf: Node with no children
• Edge: Connection between nodes
• Path: Sequence of edges from one node to another
• Depth: Number of edges from root to a node
• Height: Maximum depth of any node in the tree
• Degree: Number of children a node has

Image generated from Mermaid

📊 Tree Types

1. Binary Tree

• Each node has at most 2 children (left and right)

Image generated from Mermaid

2. Binary Search Tree (BST)

• Left subtree contains nodes with values < current node
• Right subtree contains nodes with values > current node
• Enables efficient search (O(log n) average case)

Image generated from Mermaid

3. Complete Binary Tree

• All levels are filled except possibly the last
• Last level is filled from left to right

Image generated from Mermaid

4. Full Binary Tree

• Every node has 0 or 2 children

Image generated from Mermaid

5. Perfect Binary Tree

• All internal nodes have 2 children
• All leaves are at the same level

Image generated from Mermaid

🏗️ Tree Node Implementation

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

// Constructors
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

🔄 Tree Traversals

Tree Structure

         1
     /       \
    2         3
   / \       / \
  4   5     6   7
 / \   /   /   / 
8   9 10  11  12
               \
                13 

1. Depth-First Search (DFS)

Inorder Traversal (Left → Root → Right)

// Recursive
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorderHelper(root, result);
    return result;
}

private void inorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorderHelper(node.left, result);
    result.add(node.val);
    inorderHelper(node.right, result);
}

// Iterative
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {

// Go to leftmost node
while (current != null) {
            stack.push(current);
            current = current.left;
        }

// Process current node
        current = stack.pop();
        result.add(current.val);

// Move to right subtree
        current = current.right;
    }
    return result;
}

// OUTPUT: 8, 4, 9, 2, 10, 5, 1, 11, 6, 3, 12, 7, 13

Preorder Traversal (Root → Left → Right)

// Recursive
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderHelper(root, result);
    return result;
}

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);
    preorderHelper(node.left, result);
    preorderHelper(node.right, result);
}

// Iterative
public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        result.add(current.val);

// Push right first (so left is processed first)
if (current.right != null) stack.push(current.right);
        if (current.left != null) stack.push(current.left);
    }
    return result;
}

//OUTPUT: 1, 2, 4, 8, 9, 5, 10, 3, 6, 11, 7, 12, 13

Postorder Traversal (Left → Right → Root)

// Recursive
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderHelper(root, result);
    return result;
}

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorderHelper(node.left, result);
    postorderHelper(node.right, result);
    result.add(node.val);
}

// Iterative (using two stacks)
public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode current = stack1.pop();
        stack2.push(current);
        if (current.left != null) stack1.push(current.left);
        if (current.right != null) stack1.push(current.right);
    }
    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    return result;
}

//OUTPUT: 8, 9, 4, 10, 5, 2, 11, 6, 12, 13, 7, 3, 1

2. Breadth-First Search (BFS) / Level Order Traversal

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode current = queue.poll();
            currentLevel.add(current.val);
            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
        result.add(currentLevel);
    }
    return result;
}

//OUTPUT: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13