1/22
Vocabulary flashcards covering foundational concepts, operations, and classifications for Stacks, Queues, and Binary Trees based on the exam preparation notes.
Stack
A linear data structure that follows LIFO (last in, first out) order, where push, pop, and peek/top operations all occur at one end (the top) in O(1) time.
Monotonic Stack
A stack whose elements are kept in strictly increasing or decreasing order by popping elements that break the order before pushing new elements, running in O(n) total time.
Next Greater Element (NGE)
A problem solved in O(n) time by traversing an array from right to left using a decreasing stack, popping elements while stack.top≤x and recording the top element.
Min Stack
A stack variant that supports retrieving the minimum element in O(1) time, typically implemented using an auxiliary stack to record the running minimum or by storing (value,minSoFar) pairs.
Queue
A linear data structure that follows FIFO (first in, first out) order, inserting elements at the rear (enqueue) and removing elements from the front (dequeue).
Circular Queue
A fixed-size array queue implementation that reuses empty front slots by wrapping indices using modulo arithmetic: rear=(rear+1)%size and front=(front+1)%size.
Binary Tree
A hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.
Root
The topmost node in a tree hierarchy from which all other nodes descend.
Leaf
A node in a tree that has no children.
Depth (of a Node)
The number of edges on the path from the root node to the specified node.
Height (of a Node)
The number of edges (or nodes, depending on convention) on the longest downward path from the node to a leaf.
Level (of a Node)
A measure defined as depth+1 when the root node is considered level 1.
Full Binary Tree
A binary tree in which every node has either 0 or 2 children.
Complete Binary Tree
A binary tree where all levels are completely filled except possibly the last level, which is filled from left to right.
Perfect Binary Tree
A binary tree in which all interior nodes have exactly 2 children and all leaf nodes are at the same level.
Balanced Binary Tree
A binary tree in which the height difference between the left and right subtrees of every node is at most 1.
Skewed Binary Tree
A binary tree in which every internal node has only one child, causing the tree to degrade into a linear structure.
Pre-order Traversal
A depth-first traversal that visits nodes in the order: Root, Left subtree, Right subtree (useful for copying a tree).
In-order Traversal
A depth-first traversal that visits nodes in the order: Left subtree, Root, Right subtree (produces elements in ascending sorted order for a binary search tree).
Post-order Traversal
A depth-first traversal that visits nodes in the order: Left subtree, Right subtree, Root (used for deleting a tree or evaluating expression trees).
Level Order Traversal
A breadth-first tree traversal implemented using a queue that visits nodes level by level from left to right.
Diameter of a Binary Tree
The length of the longest path between any two nodes in a binary tree, measured in edges, which may or may not pass through the root.
Maximum Path Sum
The highest sum of node values along any path in a binary tree that starts and ends at any nodes and follows parent-child links.