DSA

Binary Tree

• allows data to be organized hierarchically, making it valuable in scenarios where data relationship exists.

• it can have up to two (2) child nodes per parent.

Root node

Topmost mode of this tree

two (2)

Every parent node may have only __ children (left/right child)

Data Element

Functions as a storage for the data value that the node needs to store

Pointer to the Left Child

holds the address to the Left child node.

Pointer to the Right Child

holds the address to the Right child node.

Tree Traversal

• process of visiting every node in a tree exactly once in a particular order to access or process data.

Breadth-First Traversal

• also known as Level Order Traversal

• visits the nodes level by level from the root downwards, moving horizontally across each level before descending to the next.

Depth-First Traversal

the traversal proceeds by exploring as deeply as possible along each branch before backtracking.

Inorder Traversal

• LVR

• This method is particularly useful in binary search trees because it retrieves values in a naturally sorted order.

Preorder Traversal

• VLR

• Commonly applied in tasks such as creating a duplicate of the tree or evaluating prefix expressions.

Postorder Traversal

• LRV

• useful when a task requires processing child nodes before their parent node (safely deleting a tree/evaluating postfix expression).

Binary Search Tree (BST)

• used for retrieving, sorting, and searching data.

• Ordered Binary Tree

Hierarchical Data Representation

• represents file systems (directories contain subdirectories & files in a tree-like format).

• DOM in HTML/XML docs use tree structures to illustrate nested relationships clearly.

Efficient Searching and Sorting

• BST, AVL, and Red-Black Trees provide fast access, insertion, and deletion operations.

• Ensures that these operations remain efficient (esp w/ frequent data updates).

Databases and File Storage Systems

• Relies heavily on tree structures (B- Trees & B+ Trees)

• used to manage large volumes of data and support efficient indexing & range queries (MySQL & Oracle)

• Tries (prefix trees)  are used for fast retrieval in applications such as autocomplete systems, dictionary lookups, & IP routing in networks.

AI & Game Development

• trees play a central role.

• decision trees are commonly used for classification problems in machine learning.

• minimax trees guide decision-making in competitive games like chess (optimized using alpha-beta pruning).

• Behavior trees widely used in modern video games to control NPC behavior in a structured and modular way.

Compiler Design

• rely on Abstract Syntax Trees (AST) to represent the syntactic structure of programming languages (parse and analyze code efficiently).

• Parse trees also help visualize the grammatical structures of code inputs.

Cryptography and Security

• Merkle Trees (blockchain technologies like BTC and ETH), facilitates fast and secure verification of transaction.

• Authentication systems also use the tree structures to organize & verify credentials efficiently.

Networking

• trees are essential for building routing tables and performing fast IP lookups using trie structures.

• Minimum Spanning Tree (MST), employed through Kruskal’s or Prim’s algo, are used to optimize network designs by minimizing connection costs.

Heap Data Structure

• binary tree in which every node is larger than the values associated with either child.

• largest/smallest value is always at the top (root) of the tree.

Max-Heap

• the parent node is always greater than/equal to its children.

• largest value is always at the root of the tree.

Heapsort

(Max-Heap)

• comparison-based sorting algo that uses a binary heap to repeatedly extract the max/min element and place it at the end of array.

• it uses a max-heap to sort an array in ascending order by repeatedly extracting the max and placing it at the end.

Priority Queues (Max-Heap)

• element with the highest priority is accessed first, such as real-time operating systems (RTOS) and emergency resource allocation systems.

• put the “(Min-Heap) or (Max-Heap)” at the end of your answer

Top-K tracking

• process of efficiently maintaining the K largest or K smallest elements from a continuous stream or large dataset, without sorting the entire input.

• size of K is used to find the K smallest elements (max-heap). New elements are compared to the root (largest); if smaller value, it is replaced,

• applied in product-ranking systems (bottom K-scores) & real-time performance analytics (slowest transactions).

Min-Heap

• the parent node is always less than/equal to its children.

• smallest value is always at the root of the tree.

Dijkstra’s Algorithm

• uses min-heap to extract the next closest vertex (smallest tentative distance).

• applied in GPS routing, network routing protocols & game AI pathfinding.

Priority Queues (Min-Heap)

• this are the backbone of priority queues (task with lowest cost are processed first).

• applied in CPU scheduling (shortest-job-first), task sched in OS, and printer job management.

• put the “(Min-Heap) or (Max-Heap)” at the end of your answer.

Event-Driven Simulation

• stores and retries the next event based on the timestamp.

• min-heap ensures earlier event is always at the top.

• applied in network simulations, manufacturing process simulations, logistics & supply chain modeling.

Insert (Push)

adds a new element to the heap by adding it at the bottom

Extract Root (Pop)

removes and returns the root element with the last element

Peek (Get Root)

returns the root without removing it.

Replace

removes the root and inserts a new element in a single operation.

Heapify

• process of converting an arbitrary array (no specific structure/order) to a valid heap.

• heap property (parent >= or <= children) is maintained from a given node down to its descendants.

Up-Heapify (Bubble-Up)

• used after inserting a new element to restore the heap property by moving the element up the tree.

Down-Heapify (Bubble-Down)

• used after deleting the root element to restore the heap property by moving the new root element down the tree.

Priority Queues

• abstract data type that operates like a regular queue, except that each element priority level, and elements are dequeued based on their priority, not just their arrival order.

• elements with higher priority are processed first.

Implementing Insert

When a new value is inserted into a priority queue, add the value so that the heap still has its properties.

To achieve:

• Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or complete binary, all leaves were at the same depth) ensures that the heap has its shape property.

• Compare the new value in its parents to check. If the parent is smaller, swap the values until the order property holds/reaches the root.

removeMax

This operation will always remove & return the root values.

To achieve:

• Replace the value in the root with the value at the end of the array (corresponds to rightmost leaf at depth d).

• Remove that leaf from the tree.

• From down the tree, swap the values to restore the order property: each time is the value in the current node < one of its children, then swap its value with the larger child. Ensures that the new root value > both of its children.