Binary Tree
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 one of the most fundamental structures in computer science, forming the basis for more specialized trees like binary search trees and heaps. Binary trees are widely used in expression parsing, Huffman coding, and database indexing.
Binary Tree Traversal Methods and Their Properties
| Traversal | Order | Use Case | Time Complexity |
|---|---|---|---|
| In-order | Left → Root → Right | Sorted output in BST | O(n) |
| Pre-order | Root → Left → Right | Tree serialization | O(n) |
| Post-order | Left → Right → Root | Tree deletion | O(n) |
| Level-order | Level by level (BFS) | Shortest path problems | O(n) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Binary Search Tree
A binary search tree (BST) is a binary tree in which every node satisfies the property that all keys in its left subtree are less than the node's key and all keys in its right subtree are greater. This ordering property makes search, insertion, and deletion operations efficient, averaging O(log n) for balanced trees. BSTs are foundational in database indexing, symbol tables, and dynamic set operations.
Heap (data structure)
A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, each parent node is greater than or equal to its children; in a min-heap, each parent is less than or equal to its children. Heaps are typically implemented as complete binary trees stored in arrays, enabling O(1) access to the minimum or maximum element. They are the underlying structure of priority queues and are used in heap sort and Dijkstra's shortest path algorithm.
AVL Tree
An AVL tree is a self-balancing binary search tree in which the difference in heights between the left and right subtrees (the balance factor) of any node is at most 1. Named after its inventors Adelson-Velsky and Landis (1962), it was the first self-balancing BST ever invented. The tree automatically performs rotations (single or double) during insertions and deletions to maintain balance, guaranteeing O(log n) time for all operations.
The word "binary" derives from the Latin "binarius," meaning "consisting of two." The term has been used in computer science since the 1960s to describe tree structures where each node branches into at most two children.