DSA MIDTERMS

Binary Tree

A hierarchical data structure where each node has at most two children (left and right).

Root

The topmost node in a binary tree.

Leaf Node

A node with no children (both left and right are NULL).

Node Fields

Data element, pointer to left child, pointer to right child.

Tree Traversal

The process of visiting every node in a tree exactly once in a particular order.

Breadth—First Traversal (BFT)

Also known as Level Order Traversal; visits nodes level by level using a queue.

Depth—First Traversal (DFT)

Explores as deeply as possible along one branch before backtracking.

Inorder Traversal

Visits left subtree, root, then right subtree (L → Root → R). In BST, this yields sorted order.

Preorder Traversal

Visits root, then left subtree, then right subtree (Root → L → R). Used in tree copying.

Postorder Traversal

Visits left subtree, then right subtree, then root (L → R → Root). Used in deleting trees.

Binary Search Tree (BST)

An ordered binary tree with rules: left child < parent < right child, no duplicates allowed.

BST Property

Both left and right subtrees must also be BSTs.

BST Unique Keys

Every node in a BST has a unique key; duplicates are not allowed.

BST Rule Left

Left subtree contains only nodes with keys less than the parent.

BST Rule Right

Right subtree contains only nodes with keys greater than the parent.

AVL Tree

A self—balancing Binary Search Tree.

AVL Balanced

BF must be —1, 0, or +1.

AVL Unbalanced

If BF < —1 or BF > +1, the tree needs rotations.

LL Rotation

Right rotation used when the tree is left—left heavy.

RR Rotation

Left rotation used when the tree is right—right heavy.

LR Rotation

Left rotation on child, then right rotation on parent (zig—zag case).

RL Rotation

Right rotation on child, then left rotation on parent (zig—zag case).

Heap

A complete binary tree that satisfies the heap order property.

Heap Shape Property

A heap is always a complete binary tree (all levels filled, last filled left to right).

Heap Order Property

Parent is always ≥ children (max—heap) or ≤ children (min—heap).

Max—Heap

Parent ≥ children, largest value always at the root.

Min—Heap

Parent ≤ children, smallest value always at the root.

Heap Operations

Insert, Extract Root, Peek, Replace.

Heapify

Process of restoring heap property after insertion or deletion.

Up—Heapify (Bubble Up)

Used after insertion to restore heap property by moving the element up.

Down—Heapify (Bubble Down)

Used after deletion of root to restore heap property by moving the root down.

Priority Queue

Abstract data type where elements are dequeued based on priority, not arrival order.

Priority Queue with Heap

Implemented using a heap for fast insertion and extraction.