Data Structures & Tree Traversal Lab
Build and manipulate stacks, queues, linked lists, and binary search trees. Visualize operations in real time, run tree traversals to see visit order, and benchmark performance to understand why different structures excel at different tasks.
Guided Experiment: LIFO vs FIFO
If you push the numbers 1, 2, 3, 4, 5 into both a stack and a queue, then remove all elements, will the order be the same or different? Why?
Write your hypothesis in the Lab Report panel, then click Next.
Push values to see the visualization.
Controls
Stack Info
Perform operations to see history and results here.
Data Table
(0 rows)| # | Structure | Operation | Value | Result | Size After | Time Complexity |
|---|
Reference Guide
Stack & Queue
A stack follows Last In, First Out (LIFO) order. Think of a stack of plates. The last plate placed on top is the first one removed.
A queue follows First In, First Out (FIFO) order. Think of a line at a store. The first person in line is the first served.
Both push/pop (stack) and enqueue/dequeue (queue) are O(1) operations because they only modify one end of the structure.
Linked Lists
A linked list stores elements in nodes, where each node points to the next. Unlike arrays, elements are not stored in contiguous memory.
Inserting at the head is O(1) because you only update one pointer. Searching is O(n) because you must traverse from the head.
Linked lists are ideal when you need frequent insertions and deletions at the beginning, but random access is not needed.
Binary Search Trees
A BST is a tree where every node's left children have smaller values and right children have larger values. This property enables efficient search.
Average case for insert, search, and delete is O(log n) because each comparison eliminates half the remaining nodes.
Worst case is O(n) when the tree becomes a straight line (all insertions in sorted order). Self-balancing trees like AVL and Red-Black trees avoid this problem.
Tree Traversals
Inorder (Left, Root, Right) produces sorted output for a BST. Used to retrieve elements in order.
Preorder (Root, Left, Right) visits the root first. Used to create a copy of the tree.
Postorder (Left, Right, Root) visits the root last. Used to safely delete a tree (children before parent).
Level-order (BFS) visits nodes by depth, left to right. Uses a queue internally.