Tree Data Structure – Complete Guide with Java Programs

🌳 Tree Data Structure – Complete Guide (Java)

This blog post is a complete start-to-end guide on Tree Data Structures. It covers theory, terminology, diagrams, and multiple Java programs with clear explanations. You can use this post for learning, revision, or reference.

---

1️⃣ What is a Tree?

A Tree is a non-linear hierarchical data structure made of nodes connected by edges. It represents parent–child relationships.

• Topmost node is called the root
• Each node can have zero or more children
• No cycles are allowed

Example

    A
   / \
  B   C

---

2️⃣ Tree Terminology

• Node: Basic unit of a tree
• Root: Topmost node
• Parent: Node having children
• Child: Node derived from a parent
• Leaf: Node with no children
• Sibling: Nodes with same parent
• Height: Longest path from node to leaf (edges)
• Depth: Distance from root to node
• Size: Total number of nodes

---

3️⃣ Tree Node Structure (Java)

class Node {
    int data;
    Node left, right;

```
Node(int data) {
    this.data = data;
    left = right = null;
}
```

}

This node structure is reused for all binary tree programs.

---

4️⃣ Sample Tree Used in Programs

        10
       /  \
      5    15
     / \   / \
    2   7 12  20

---

5️⃣ Depth First Search (DFS)

DFS explores one branch completely before moving to another. There are three DFS traversals.

Inorder Traversal (LNR)

static void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}

Output: 2 5 7 10 12 15 20

---

Preorder Traversal (NLR)

static void preorder(Node root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    preorder(root.left);
    preorder(root.right);
}

Output: 10 5 2 7 15 12 20

---

Postorder Traversal (LRN)

static void postorder(Node root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.data + " ");
}

Output: 2 7 5 12 20 15 10

---

6️⃣ Breadth First Search (BFS – Level Order)

BFS traverses the tree level by level using a Queue.

static void levelOrder(Node root) {
    if (root == null) return;

    Queue<Node> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
        Node curr = q.poll();
        System.out.print(curr.data + " ");

        if (curr.left != null) q.add(curr.left);
        if (curr.right != null) q.add(curr.right);
    }
}

Output: 10 5 15 2 7 12 20

---

7️⃣ Binary Search Tree (BST)

A BST is a Binary Tree with ordering rule:

• Left subtree values < root
• Right subtree values > root

BST Insert

static Node insertBST(Node root, int val) {
    if (root == null)
        return new Node(val);

```
if (val < root.data)
    root.left = insertBST(root.left, val);
else
    root.right = insertBST(root.right, val);

return root;
```

}

---

8️⃣ Additional Tree Programs

Height of Tree

static int height(Node root) {
    if (root == null) return -1;
    return 1 + Math.max(height(root.left), height(root.right));
}

Size of Tree

static int size(Node root) {
    if (root == null) return 0;
    return 1 + size(root.left) + size(root.right);
}

Count Leaf Nodes

static int countLeaves(Node root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    return countLeaves(root.left) + countLeaves(root.right);
}

Mirror a Tree

static void mirror(Node root) {
    if (root == null) return;

```
Node temp = root.left;
root.left = root.right;
root.right = temp;

mirror(root.left);
mirror(root.right);
```

}

---

9️⃣ Root-to-Leaf Paths

static void printPaths(Node root, List<Integer> path) {
    if (root == null) return;

```
path.add(root.data);

if (root.left == null && root.right == null)
    System.out.println(path);

printPaths(root.left, path);
printPaths(root.right, path);

path.remove(path.size() - 1);
```

}

---

10️⃣ Conclusion

You now have a complete Tree Data Structure reference including theory, diagrams, DFS, BFS, BST, and multiple utility programs. This blog can be used for both learning and quick revision.