Binary trees are hierarchical structures that provide flexible and powerful ways to organize data. The performance of common operations in a binary tree—such as insertion, deletion, traversal, and search—depends on the shape of the tree. In a balanced binary tree, most operations take logarithmic time. However, in the worst case, performance may degrade to linear time.
Summary Table
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Insertion | O(1) | O(log N) | O(N) |
| Deletion | O(log N) | O(log N) | O(N) |
| Traversal | O(N) | O(N) | O(N) |
| Search | O(1) | O(log N) | O(N) |
| Height | O(log N) | O(log N) | O(N) |
| Count Nodes | O(N) | O(N) | O(N) |
| Count Leaf Nodes | O(N) | O(N) | O(N) |
| Mirror / Invert | O(N) | O(N) | O(N) |
1. Insertion
Inserting a node in a binary tree can be done level-wise (in a complete binary tree) or by rules (in a BST). In general binary trees, you may insert at the first vacant position using BFS.
- Best Case – O(1): If the root is empty or you insert at the first available spot.
- Average Case – O(log N): In a balanced tree, finding the right location takes log N time.
- Worst Case – O(N): In a skewed tree (like a linked list), traversal from root to deepest node is required.
2. Deletion
Deleting a node in a binary tree involves three scenarios: deleting a leaf, a node with one child, or a node with two children. In general trees, deletion may involve swapping with the deepest node.
- Best Case – O(log N): Balanced tree and deleting a leaf node.
- Average Case – O(log N): Most deletions occur mid-tree, with log N traversal time.
- Worst Case – O(N): In a skewed tree, you may traverse all nodes to find the one to delete.
3. Traversal
Traversal involves visiting every node in the tree. Types include in-order, pre-order, post-order, and level-order.
- Best/Average/Worst Case – O(N): All nodes are visited exactly once in every traversal type.
4. Search
Searching involves checking whether a value exists in the tree.
- Best Case – O(1): If the root node matches the search value.
- Average Case – O(log N): In a balanced tree, value is likely to be found within log N steps.
- Worst Case – O(N): Skewed or unbalanced trees may require checking all nodes.
5. Height Calculation
The height of a binary tree is the number of nodes on the longest path from root to a leaf.
- Best Case – O(log N): In a balanced tree.
- Average Case – O(log N): Tree height typically grows logarithmically with node count.
- Worst Case – O(N): In an unbalanced tree where all nodes are in one branch.
6. Count Total Nodes
To count all nodes, each node must be visited.
- All Cases – O(N): Every node is counted individually during a full traversal.
7. Count Leaf Nodes
Leaf nodes are those with no children. You must visit each node to check if it’s a leaf.
- All Cases – O(N): All nodes must be visited to determine which are leaves.
8. Mirror / Invert Tree
Mirroring a binary tree means swapping left and right children recursively for all nodes.
- All Cases – O(N): You must visit and modify each node once.