What is a Binary Tree?

A binary tree is a tree data structure where each node has at most two children (left and right). Think of it like a family tree, but each person can only have two children maximum.

Key Properties:

• Each node has 0, 1, or 2 children
• Left child is smaller (in sorted trees)
• Right child is larger (in sorted trees)
• Root: The top node
• Leaf: Nodes with no children

Types:

• Binary Search Tree (BST): Left < Parent < Right
• Balanced tree: Height is minimized (like AVL, Red-Black)
• Complete tree: All levels filled except possibly the last

Why They're Useful:

• Fast search: O(log n) in balanced trees
• Sorted data: Maintains order automatically
• Hierarchical data: Perfect for representing relationships

Traversal Methods:

• In-order: Left, Root, Right (gives sorted order)
• Pre-order: Root, Left, Right
• Post-order: Left, Right, Root