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

Get Saumya14’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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