Stacks, Queues & Binary Trees – Exam Prep

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/22

flashcard set

Earn XP

Description and Tags

Vocabulary flashcards covering foundational concepts, operations, and classifications for Stacks, Queues, and Binary Trees based on the exam preparation notes.

23 Terms

1
New cards

Stack

A linear data structure that follows LIFOLIFO (last in, first out) order, where pushpush, poppop, and peekpeek/toptop operations all occur at one end (the top) in O(1)O(1) time.

2
New cards

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)O(n) total time.

3
New cards

Next Greater Element (NGE)

A problem solved in O(n)O(n) time by traversing an array from right to left using a decreasing stack, popping elements while stack.top≤x\text{stack.top} \le x and recording the top element.

4
New cards

Min Stack

A stack variant that supports retrieving the minimum element in O(1)O(1) time, typically implemented using an auxiliary stack to record the running minimum or by storing (value,minSoFar)(value, minSoFar) pairs.

5
New cards

Queue

A linear data structure that follows FIFOFIFO (first in, first out) order, inserting elements at the rear (enqueueenqueue) and removing elements from the front (dequeuedequeue).

6
New cards

Circular Queue

A fixed-size array queue implementation that reuses empty front slots by wrapping indices using modulo arithmetic: rear=(rear+1)%sizerear = (rear + 1) \% size and front=(front+1)%sizefront = (front + 1) \% size.

7
New cards

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.

8
New cards

Root

The topmost node in a tree hierarchy from which all other nodes descend.

9
New cards

Leaf

A node in a tree that has no children.

10
New cards

Depth (of a Node)

The number of edges on the path from the root node to the specified node.

11
New cards

Height (of a Node)

The number of edges (or nodes, depending on convention) on the longest downward path from the node to a leaf.

12
New cards

Level (of a Node)

A measure defined as depth+1depth + 1 when the root node is considered level 11.

13
New cards

Full Binary Tree

A binary tree in which every node has either 00 or 22 children.

14
New cards

Complete Binary Tree

A binary tree where all levels are completely filled except possibly the last level, which is filled from left to right.

15
New cards

Perfect Binary Tree

A binary tree in which all interior nodes have exactly 22 children and all leaf nodes are at the same level.

16
New cards

Balanced Binary Tree

A binary tree in which the height difference between the left and right subtrees of every node is at most 11.

17
New cards

Skewed Binary Tree

A binary tree in which every internal node has only one child, causing the tree to degrade into a linear structure.

18
New cards

Pre-order Traversal

A depth-first traversal that visits nodes in the order: Root, Left subtree, Right subtree (useful for copying a tree).

19
New cards

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).

20
New cards

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).

21
New cards

Level Order Traversal

A breadth-first tree traversal implemented using a queue that visits nodes level by level from left to right.

22
New cards

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.

23
New cards

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.