MainExamplesHistoryRecommended Reading
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
FAQ
What's the difference between a tree and a binary tree?
A tree can have any number of children per node. A binary tree is restricted to at most two children per node.
Why are balanced trees important?
Unbalanced trees can become like linked lists (O(n) worst case). Balanced trees maintain O(log n) performance.