Time Complexity of Binary Tree Operations

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.