Binary Tree in Java

1. What is a Binary Tree?

A Binary Tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and right child.

Each node in a binary tree contains:

Data (or a value)
A reference to the left child
A reference to the right child

A Binary Tree follows a recursive structure—every child is itself a binary tree.

2. Types of Binary Trees

a. Full Binary Tree

Every node has either 0 or 2 children.

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

b. Complete Binary Tree

All levels are completely filled except possibly the last level, and all nodes are as left as possible.

c. Perfect Binary Tree

All internal nodes have two children and all leaves are at the same level.

        1
      /   \
     2     3
    / \   / \
   4  5  6   7

d. Balanced Binary Tree

The height difference between left and right subtrees for any node is at most 1.

e. Degenerate (or Skewed) Tree

Each parent has only one child. It becomes like a linked list.

3. Binary Tree Representation in Java

A Binary Tree is typically represented using Nodes where each node stores the data and references to its left and right children.

Node Class

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

    public TreeNode(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

BinaryTree Class

public class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }
}

4. Use Cases and Applications

Hierarchical data representation (e.g., file systems)
Binary Search Trees: Fast search, insert, delete
Expression trees: Evaluation of expressions
Priority Queues: Implemented using binary heaps
Huffman Encoding Trees: Used in data compression