Data Structure

Array

Static Array

In static array, memory is allocated at compile time having a fixed size of it. We can't change the size of the array once it is declared.

In C++, arr[0] is the starting address of the array, and arr[1] is the address of the next element (i.e., arr[0] + sizeof(xx)).
arr is a pointer to the first element of the array, i.e., *arr = arr[0] or arr= &arr[0].
The memory of the array is contiguous.

Time Complexity

Retrieval & Modification: O(1).
Insertion & Deletion (not at the end): O(N).
If full, we can't insert more elements as the size is fixed. A new array will be created and elements will be copied to the new array with time complexity O(N).

Dynamic Array

Dynamic array is based on static array. It automatically handles resizing and other operations with built-in functions.

Linked List

Compared to arrays, linked lists do not store data in contiguous memory locations. Instead, each element points to the next element. Thus, having following pros and cons:

Pros: 1. No need for contiguous memory. 2. Easy insertion and deletion with O(1) time complexity

Cons: 1. Access requires traversing the list with O(N) time complexity.

Hash Table

Hash table uses a hash function to compute an index into an array of buckets, from which the desired value can be found.

Hash collision

When two keys hash to the same index, it is called a hash collision. There are several ways to handle hash collisions:

Chaining: Each bucket contains a linked list of elements, and when a collision occurs, the element is added to the list.
Open Addressing: When a collision occurs, the algorithm searches for the next open slot in the hash table.

Load factor is the ratio of the number of elements to the number of buckets. A high load factor results in more collisions. When the load factor exceeds a threshold, the hash table needs to be resized.

Binary Tree

Binary Search Tree

In a binary search tree (BST), the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree only contains nodes with keys greater than the node's key:

Note that the following tree is not a BST because the right child of 4 is greater than 7.

Recursive/Level Traversal

Depth-First Search (DFS)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def traverse(root: TreeNode):
    if root is None:
        return
    # Code for pre-order traversal
    traverse(root.left)
    # Code for in-order traversal
    traverse(root.right)
    # Code for post-order traversal

Note that here the order of traversal is fixed. The pre-order, in-order, and post-order traversals differ in the order of visiting the root node.

Breadth-First Search (BFS)

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    while q:
        cur = q.popleft()
        print(cur.val)

        if cur.left is not None:
            q.append(cur.left)
        if cur.right is not None:
            q.append(cur.right)

DFS vs. BFS

BFS is usually used for finding the shortest path as BFS traverses all nodes at the current depth before moving to the next depth.
DFS is usually used for finding all possible paths as DFS goes as deep as possible before backtracking.

N-ary Tree

An N-ary tree is a tree in which each node has at most N children.

Forest

Forest is a collection of disjoint trees. A forest can be represented as a list of trees.

DFS on N-ary Tree

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def traverse(root: Node):
    if root is None:
        return
    # Code for pre-order traversal
    for child in root.children:
        traverse(child)
    # Code for post-order traversal

BFS on N-ary Tree

from collections import deque

def level_order_traverse(root):
    if root is None:
        return

    q = deque()
    q.append(root)

    while q:
        cur = q.popleft()

        print(cur.val)

        for child in cur.children:
            q.append(child)

Heap

Binary heap is a complete binary tree that is complete and obeys min-heap property.

Min-heap: Every node is less than or equal to its children.
Complete: Missing nodes are only at the bottom level and to the right.

The following is not a heap as it is not complete:

Heap Add

To insert an element into a heap, we need:

Add the element to the end of the heap.
Swim up the element (swap with its parent) until the heap property is satisfied.

Heap Delete

To delete the root element from a heap, we need:

Replace the root with the last element.
Sink down the element (swap with its child) until the heap property is satisfied.