Scribd
Upload
3 views2 pages

Essential DSA Exam Notes Summary

The document provides notes on various data structures and algorithms (DSA) including stacks, queues, trees, graphs, AVL trees, hash tables, sorting algorithms, and binary search trees. It outlines key operations, types, and applications for each structure, along with traversal methods and classifications of DSA. Additionally, it covers the properties of red-black trees and their operational complexities.

Uploaded by

zana.irm
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Essential DSA Exam Notes Summary

The document provides notes on various data structures and algorithms (DSA) including stacks, queues, trees, graphs, AVL trees, hash tables, sorting algorithms, and binary search trees. It outlines key operations, types, and applications for each structure, along with traversal methods and classifications of DSA. Additionally, it covers the properties of red-black trees and their operational complexities.

Uploaded by

zana.irm
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DSA Exam Notes

1. Stack

- LIFO structure.

- Operations: push, pop, peek, isEmpty.

- Applications: recursion, undo/redo, expression evaluation.

2. Queue

- FIFO structure.

- Operations: enqueue, dequeue, front, isEmpty.

- Types: simple, circular, priority, deque.

- Applications: scheduling, BFS.

3. Tree Terminologies

Node, root, parent, child, leaf, height, depth, siblings, subtree.

4. Binary Tree Traversal

- DFS: Preorder, Inorder, Postorder.

- BFS: Level order traversal.

5. Graph

- Components: vertices and edges.

- Types: directed, undirected, weighted, cyclic, connected.

- Representations: adjacency matrix, adjacency list.

6. AVL Tree

- Self■balancing BST.

- Balance factor ∈ {■1, 0, 1}.

- Rotations: LL, RR, LR, RL.


7. Hash Table

- Key■value storage using hash function.

- Collision handling: chaining, open addressing.

- Avg O(1) operations.

8. Sorting Algorithms

Bubble, Selection, Insertion (O(n²)).

Merge, Quick, Heap (O(n log n)).

9. Graph Traversal

- BFS: queue.

- DFS: stack/recursion.

10. BST

- Left < Root < Right.

- O(log n) operations in balanced BST.

11. Classification of DSA

Linear: Array, Linked List, Stack, Queue.

Non■linear: Tree, Graph.

Searching: Linear, Binary.

Sorting: Bubble, Selection, Insertion, Merge, Quick, Heap.

12. Red■Black Tree Basics

- Nodes colored red or black.

- Root is black.

- No two consecutive reds.

- Same number of black nodes on every root■leaf path.

- O(log n) operations.

You might also like