Binary tree
Binary tree
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are a fundamental structure in computer science, used for efficient searching, sorting, and hierarchical data representation.
Properties
In a binary tree, the degree of any node (the number of children) is 0, 1, or 2. The root is the topmost node, and nodes with no children are called leaves. Common variants include:
- Full binary tree – every node has 0 or 2 children.
- Complete binary tree – all levels are filled except possibly the last, which is filled from left to right.
- Perfect binary tree – all internal nodes have two children and all leaves are at the same depth.
- Binary search tree – an ordered binary tree where left subtree keys are less than the node's key and right subtree keys are greater.
- Balanced binary tree – a binary tree whose height is kept small relative to the number of nodes (e.g., AVL tree, red–black tree).
Traversals
A binary tree can be traversed in several standard orders:
- Pre-order – visit root, then left subtree, then right subtree.
- In-order – visit left subtree, root, then right subtree (produces sorted order for a binary search tree).
- Post-order – visit left subtree, right subtree, then root.
- Level-order – process nodes by depth from root to leaves, left to right (breadth-first).
History
The concept of a binary tree originated in mathematics and early computing. The term was popularized by computer scientists such as Donald Knuth in 1 , which formalized tree structures and algorithms for binary tree manipulation. Binary trees have since become a core topic in algorithms and data structures courses.
Applications
Binary trees are used in many areas:
- Binary search tree for dynamic set operations (insert, delete, lookup).
- Heap (a complete binary tree) for priority queues.
- Expression tree in compilers for parsing arithmetic expressions.
- Huffman coding tree for data compression.
- Binary space partitioning in computer graphics.
- Decision trees in machine learning.