Binary Trees
A Binary Tree is a tree where each node has at most two children, referred to as the left child and right child.
Properties of Binary Trees
- Maximum nodes at level L = 2^L (where root is at level 0)
- Maximum nodes in a tree of height H = 2^(H+1) – 1
- Minimum height for N nodes = log₂(N+1) – 1
Types of Binary Trees
1. Full Binary Tree
Every node has either 0 or 2 children (no node has only 1 child).
1
/ \
2 3
/ \
4 52. Complete Binary Tree
All levels are completely filled except possibly the last, which is filled from left to right.
1
/ \
2 3
/ \ /
4 5 63. Perfect Binary Tree
All internal nodes have 2 children and all leaves are at the same level.
1
/ \
2 3
/ \ / \
4 5 6 74. Skewed Binary Tree
All nodes have only one child (either left or right).
1 1
\ /
2 2
\ /
3 3
Binary Tree Implementation
java
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
// Constructor with root value
public BinaryTree(int data) {
root = new Node(data);
}
}
Binary Tree Traversals
There are three main ways to traverse a binary tree:
1. Inorder Traversal (Left → Root → Right)
Process:
- Visit left subtree
- Visit root
- Visit right subtree
Example:
Tree:
1
/ \
2 3
/ \
4 5
Inorder: 4 → 2 → 5 → 1 → 3Code Example (Java):
java
class BinaryTree {
Node root;
// Inorder traversal: Left -> Root -> Right
void inorderTraversal(Node node) {
if (node == null)
return;
// First recur on left subtree
inorderTraversal(node.left);
// Then print the data of node
System.out.print(node.data + " ");
// Now recur on right subtree
inorderTraversal(node.right);
}
// Wrapper method
void inorder() {
inorderTraversal(root);
}
// Main method to test
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Inorder Traversal:");
tree.inorder(); // Output: 4 2 5 1 3
}
}2. Preorder Traversal (Root → Left → Right)
Process:
- Visit root
- Visit left subtree
- Visit right subtree
Example:
Tree:
1
/ \
2 3
/ \
4 5
Preorder: 1 → 2 → 4 → 5 → 3Code Example (Java):
java
class BinaryTree {
// Preorder traversal: Root -> Left -> Right
void preorderTraversal(Node node) {
if (node == null)
return;
// First print data of node
System.out.print(node.data + " ");
// Then recur on left subtree
preorderTraversal(node.left);
// Now recur on right subtree
preorderTraversal(node.right);
}
// Wrapper method
void preorder() {
preorderTraversal(root);
}
}
// Usage:
// tree.preorder(); // Output: 1 2 4 5 33. Postorder Traversal (Left → Right → Root)
Process:
- Visit left subtree
- Visit right subtree
- Visit root
Example:
Tree:
1
/ \
2 3
/ \
4 5
Postorder: 4 → 5 → 2 → 3 → 1Code Example (Java):
java
class BinaryTree {
// Postorder traversal: Left -> Right -> Root
void postorderTraversal(Node node) {
if (node == null)
return;
// First recur on left subtree
postorderTraversal(node.left);
// Then recur on right subtree
postorderTraversal(node.right);
// Now print the data of node
System.out.print(node.data + " ");
}
// Wrapper method
void postorder() {
postorderTraversal(root);
}
}
// Usage:
// tree.postorder(); // Output: 4 5 2 3 14. Level Order Traversal (Breadth-First)
Process: Visit nodes level by level from left to right.
java
import java.util.LinkedList;
import java.util.Queue;
class BinaryTree {
// Level order traversal using Queue
void levelOrder() {
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
System.out.print(tempNode.data + " ");
// Enqueue left child
if (tempNode.left != null)
queue.add(tempNode.left);
// Enqueue right child
if (tempNode.right != null)
queue.add(tempNode.right);
}
}
}
// Usage:
// tree.levelOrder(); // Output: 1 2 3 4 5Complete Binary Tree Example
java
class BinaryTree {
Node root;
// Calculate height of tree
int height(Node node) {
if (node == null)
return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// Count total nodes
int countNodes(Node node) {
if (node == null)
return 0;
return 1 + countNodes(node.left) + countNodes(node.right);
}
// Check if tree is full binary tree
boolean isFullBinaryTree(Node node) {
// If empty tree
if (node == null)
return true;
// If leaf node
if (node.left == null && node.right == null)
return true;
// If both left and right are not null, and left & right subtrees are full
if ((node.left != null) && (node.right != null))
return isFullBinaryTree(node.left) && isFullBinaryTree(node.right);
// If none of the above
return false;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Height of tree: " + tree.height(tree.root));
System.out.println("Total nodes: " + tree.countNodes(tree.root));
System.out.println("Is Full Binary Tree: " + tree.isFullBinaryTree(tree.root));
}
}Real-World Applications
- Expression Trees: Used in compilers to parse expressions
- Huffman Coding Trees: Data compression algorithms
- Decision Trees: Machine learning and AI
- File System Hierarchy: Organizing files and folders