Data Structures & Big-O (CS 201) · Module 4 of 9
Stacks, Queues & Trees
LIFO and FIFO structures, and the hierarchical structure that makes ordered search efficient — when balanced.
Stacks & Queues: Implementation & Use Cases
- A stack (LIFO) can be implemented with an array or linked list, supporting O(1) push/pop; used in function call stacks, undo features, and depth-first search.
- A queue (FIFO) supports O(1) enqueue/dequeue when implemented properly — for example with a circular buffer or a linked list with head and tail pointers — and is used in task scheduling and breadth-first search.
Why is a naive array-based queue, removing from the front, inefficient, and how is this usually fixed?
Solution. Removing from the front of a plain array requires shifting all remaining elements, costing O(n); this is fixed by using a circular buffer (wrapping indices around) or a linked list with both head and tail pointers, both allowing O(1) enqueue and dequeue.
Binary Search Trees
- A binary search tree (BST) maintains the invariant that for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
- Search, insertion, and deletion in a BST are O(h), where h is the tree's height — O(log n) if balanced, but O(n) in the worst case, such as a degenerate, list-like tree.
Why can a binary search tree's operations degrade to O(n) in the worst case?
Solution. If elements are inserted in sorted order (or another pathological order), the tree can become completely unbalanced, essentially becoming a linked list with height n, making search, insertion, and deletion all take O(n) time.
Balanced Trees
- Self-balancing trees, like AVL trees and red-black trees, automatically perform rotations after insertions and deletions to keep the tree height at O(log n), guaranteeing O(log n) operations even in the worst case.
- AVL trees are more rigidly balanced (faster lookups) while red-black trees allow slightly more imbalance (faster insertions/deletions), a common trade-off between the two.
Why do self-balancing trees guarantee O(log n) operations even in the worst case, unlike a plain BST?
Solution. They actively perform rotations after modifications to maintain a height that's always proportional to log n, preventing the tree from ever degenerating into a linear, list-like structure.
Tree Traversals
- In-order traversal (left, root, right) visits a BST's nodes in sorted order; pre-order (root, left, right) and post-order (left, right, root) are useful for copying a tree or deleting it safely, respectively.
- All traversals take O(n) time, since each node must be visited exactly once.
Why does an in-order traversal of a binary search tree visit nodes in sorted order?
Solution. Because the BST invariant guarantees every node's left subtree contains smaller values and its right subtree contains larger values, visiting left subtree → node → right subtree at every step naturally produces values in ascending order.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What is the time complexity of push/pop on a properly implemented stack?
2. Why is a naive array-based queue inefficient for dequeuing from the front?