Data Structures

Implementation of various Data Structure algorithms

Tree

Terminology:

• Tree
• Node
• Root
• Edge
• Leaf
• Depth - Distance from Root to node
• Height - Distance from leaf to node
• Level - Root is at Level 0, it's children are at level 1 and so on..
• Ancestor
• Children

Binary Tree:

• 0, 1, 2 children
• Left and Right child
• Complete Binary tree
• Full Binary tree - All have 2 children

Binary Search Tree:

• Insertion, Deletion, Retrieval in O(log N)
• Left smaller than parent, right larger

Advanced Topics:

• Self-Balancing Trees
• AVL, Red-Black Tree

Operations:

1. Add
2. Traversals:
   • Level: Visit nodes on each level
   • Pre-order: Visit root first (Root, Left, Right)
   • Post-order: Visit root last (Left, Right, Root)
   • In-order: Visit left, root, right (Returns sorted data)
3. Search
4. Min
5. Max
6. Delete

Array

Operations:

1. Search
   1. LinearSearch
   2. BinarySearch
   3. JumpSearch
2. Sort
   1. JumpSearch
   2. JumpSearch
   3. InsertionSort
   4. MergeSort
   5. HeapSort

LinkedList

Operations:

1. AddFirst
2. AddLast
3. AddAfterMiddle
4. RemoveFirst
5. RemoveLast
6. RemoveAfterMiddle
7. RemoveWhere
8. Length

Queue

Operations:

1. Pop
2. Push

Stack

Operations:

1. Pop
2. Push