Course contentsShow
← Computer Science
Lesson 526 of 2,87212. Binary Search TreesFree lesson

Comparing BST to Array and Linked List

Performance comparison of BSTs versus arrays and linked lists for search, insert, and delete operations.

Comparing BST to Array and Linked List

What you'll learn: You'll understand when Binary Search Trees outperform or underperform compared to arrays and linked lists for common operations.

When choosing a data structure, you need to weigh the tradeoffs. BSTs sit in an interesting middle ground between arrays and linked lists, offering different performance characteristics for search, insert, and delete operations.

Search Operations

Sorted Array: O(log n) with binary search, but requires the array to stay sorted.

Linked List: O(n) - must traverse linearly from the head.

BST (balanced): O(log n) - eliminates half the tree at each step.

BST (worst-case): O(n) - degenerates to a linked list shape.

Insert and Delete Operations

Array: O(n) - inserting or deleting in the middle requires shifting elements. Even appending can trigger O(n) resizing.

Linked List: O(1) if you have a pointer to the location; O(n) to find the location first.

BST (balanced): O(log n) - maintains ordering automatically while navigating the tree.

BST (worst-case): O(n) - when unbalanced.

The Big Picture

Think of it this way: arrays are fast for indexed access but slow to modify. Linked lists are fast to modify if you know where but slow to search. BSTs offer a sweet spot - logarithmic search AND modification when balanced, keeping data sorted automatically.

Arrays win when you need random access by index. Linked lists win for constant-time insertions at known positions. BSTs win when you need both efficient search and dynamic modifications with maintained order.

Key Takeaway: BSTs provide O(log n) search, insert, and delete when balanced - better than linked lists' O(n) search and competitive with sorted arrays while maintaining dynamic flexibility, but they lose their advantage when unbalanced or when you need direct index access.