WikiGalaxy
Binary Tree Overview
Introduction to Binary Trees:
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is the foundation for more advanced data structures such as binary search trees and heaps.
Binary Tree Node Structure
Node Representation:
Each node in a binary tree contains three components: data, a pointer to the left child, and a pointer to the right child.
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
Binary Tree Traversals
Traversal Methods:
There are several methods to traverse a binary tree: Inorder, Preorder, and Postorder. Each method visits nodes in a specific order.
// Inorder Traversal
void inorder(Node node) {
if (node == null)
return;
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
Binary Search Tree (BST)
BST Properties:
A Binary Search Tree is a type of binary tree where the left subtree of a node contains only nodes with keys lesser than the node’s key, and the right subtree only nodes with keys greater than the node’s key.
// Insert a node in BST
Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
}
if (key < node.data) {
node.left = insert(node.left, key);
} else if (key > node.data) {
node.right = insert(node.right, key);
}
return node;
}
Balanced Binary Trees
Balancing Techniques:
Balanced binary trees maintain their height to ensure faster operations. AVL trees and Red-Black trees are common examples of balanced binary trees.
// AVL Tree Rotation
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
return x;
}
Heap Trees
Heap Structure:
A heap is a special tree-based data structure that satisfies the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children.
// Max-Heapify function
void maxHeapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
maxHeapify(arr, n, largest);
}
}
Binary Tree Applications
Practical Uses:
Binary trees are used in various applications such as expression parsing, Huffman coding, and implementing priority queues.
Binary Tree Challenges
Common Challenges:
Handling duplicate values, balancing trees, and efficiently traversing large trees are some challenges faced when working with binary trees.
