Tree¶
- Relationship Between Binary Tree, Tree, and Graph $$ Binary\ \ Tree \subset Tree \subset Graph $$
- Types of Trees ![[Screenshot 2024-12-29 at 3.20.39 PM.png]]
- Python Implementation of Trees
Tree Traversal¶
- In order Traversal: DBEAFCG
- Pre order Traversal: ABDECFG
- Post order Traversal: DEBFGCA
- Level Order Traversal: ABCDEFG ![[Screenshot 2024-12-29 at 3.26.51 PM.png]]
In order Traversal¶
def inorder_recursive(root):
if not root:
return
inorder_recursive(root.left)
visit(root)
inorder_recursive(root.right)
def inorder_iterative(root):
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
visit(node)
node = node.right
Pre order Traversal¶
def preorder_recursive(root):
if not root:
return
visit(root)
preorder_recursive(root.left)
preorder_recursive(root.right)
def preorder_iterative(root):
stack = [root]
while stack:
node = stack.pop()
if node:
visit(node)
stack.append(node.right)
stack.append(node.left)
Post order Traversal¶
def postorder_recursive(root):
if not root:
return
postorder_recursive(root.left)
postorder_recursive(root.right)
visit(root)
def postorder_iterative(root):
stack = []
node = root
while stack or node:
if node:
stack.append(node)
node = node.left if node.left else node.right
else:
peek = stack[-1]
if peek.left and peek.left != node and peek.right != node:
node = peek.left
elif peek.right and peek.right != node:
node = peek.right
else:
visit(stack.pop())
node = None
Level order Traversal¶
def levelorder(root):
traversal = []
if not root:
return traversal
queue = deque([root])
while queue:
# start a new level
traversal.append([])
# snapshot of length of nodes on this level
current_level_nodes = len(queue)
for i in range(current_level_nodes):
node = queue.pop()
traversal[-1].append(node)
# add children for next level traversal
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)
return traversal
Binary Search Tree¶
Query¶
search¶
def search_recursive(root, target):
if root is None:
return False
if root.value == target:
return True
if target < root.value:
return search(root.left, target)
else:
return search(root.right, target)
min/max¶
successor/predecessor¶
Modify¶
insert¶
def insert(root, target):
if root.value > target:
if root.left is None:
root.left = target
else:
insert(root.left, target)
else:
if root.right is None:
root.right = target
else:
insert(root.right, target)
delete¶
Binary Search¶
def binary_search(arr, low, high, target):
# check base case
if high >= low:
mid = (high + low) // 2
# if element is present at the middle itself
if arr[mid] == target:
return mid
# if element is smaller than mid, then it can only
# be present in left subarray
elif arr[mid] > target:
return binary_search(arr, low, mid - 1, target)
# else the element can only be present in right subarray
else:
return binary_search(arr, mid + 1, high, target)
else:
# element is not present in the array
return -1
def binary_search(arr, target):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# if target is greater, ignore left half
if arr[mid] < target:
low = mid + 1
# if target is smaller, ignore right half
elif arr[mid] > target:
high = mid - 1
# target is present at mid
else:
return mid
# if we reach here, then the element was not present
return -1
Trie¶
class Node(object):
def __init__(self):
self.children = {}
self.is_end = False
def insert(node, word):
for c in word:
if c not in node.children:
node.children[c] = Node()
node = node.children[c]
node.is_end = True
def search(node, word):
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end
Heap¶
Concept¶
| features | queue | stack | heap |
|---|---|---|---|
| linearity | linear | linear | non-linear |
| order | FIFO | LIFO | follow heap property |
| types | simple queue circular queue priority queue? deque |
no types | min heap max heap |
| pointer | two pointers | one pointer | one pointer |
| capacity | not necessarily bounded | bounded | can be resized |
| usage | sequential algorithms | recursion backtracking |
heapsort |
| - max heap: parent always larger than children | |||
| - min heap: parent always smaller than children | |||
| - also a complete binary tree | |||
| - partially sorted | |||
| - heap =? priority queue |
| operation | time |
|---|---|
| push | O(logn) |
| pop | O(logn) |
| peek | O(1) |
| is empty | O(1) |
## heapq |
heapq.heappush(_heap_, _item_)
- Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(_heap_)
- Pop and return the smallest item from the heap, maintaining the heap invariant. To access the smallest item without popping it, use heap[0].
heapq.heappushpop(_heap_, _item_)
- Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
heapq.heapify(_x_)
- Transform list x into a heap, in-place, in linear time.
heapq.heapreplace(_heap_, _item_)
- Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change.
Build heap¶
- Add node to the end of array
- Swap children with parent if not heapify
- Repeat above
Heapsort¶
Priority Queue¶
Sorting¶
Graph Search¶
BFS¶
def bfs(g, s):
visited = {node: False for node in g}
queue = deque()
queue.append(s)
visited[s] = True
while queue:
s = queue.popleft()
for i in g[s]:
if visited[i] is False:
queue.append(i)
visited[i] = True
Level Traversal¶
def level_order(root):
if not root:
return []
# first level
queue = collections.deque([root])
results = []
# loop to generate next levels
while queue:
# save the current level to result
results.append([node.value for node in queue])
# expand to next level
length = len(queue)
for _ in range(length):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return results
Connected Components¶
Topological Sorting¶
- Choose the first node with 0 in-degree B, and remove it
- Choose the node with 0 in-degree E, and remove it
- Choose the node with 0 in-degree A, and remove it
- Choose the node with 0 in-degree C, and remove it
- Choose the node with 0 in-degree D, and remove it
In-degree refers to the number of incoming edges to a node in a directed graph.
![[Pasted image 20241227162204.png]]
from collections import deque def topological_sort_kahn(num_vertices, adjacency_list): """ Performs topological sort using Kahn's Algorithm (BFS approach). :param num_vertices: Number of vertices. :param adjacency_list: adjacency_list[u] = list of neighbors of u. :return: List of vertices in topologically sorted order. """ in_degree = [0] * num_vertices # Calculate in-degrees of all vertices for u in range(num_vertices): for v in adjacency_list[u]: in_degree[v] += 1 # Queue for all vertices with in-degree 0 queue = deque([i for i in range(num_vertices) if in_degree[i] == 0]) topo_order = [] while queue: current_vertex = queue.popleft() topo_order.append(current_vertex) for neighbor in adjacency_list[current_vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return topo_order
Examples: - linear ordering of nodes in a directed graph - course schedules - task scheduler
Shortest Path¶
- Step 1: Start with a weighted graph
- Step 2: Choose a starting vertex and assign infinity path values to all other devices
- Step 3: Go to each vertex and update its path length
- Step 4: If the path length of the adjacent vertex is lesser than new path length, don't update it
- Step 5: Avoid updating path lengths of already visited vertices
- Step 6: After each iteration, we pick the unvisited vertex with the least path length. So we choose 5 before 7
- Step 7: Notice how the rightmost vertex has its path length updated twice
- Step 8: Repeat until all the vertices have been visited
- O(E logV)
DFS¶
def dfs(g, s):
visited = {node: False for node in g}
stack = deque()
stack.append(s)
visited[s] = True
while stack:
s = stack.pop()
for i in g[s]:
if visited[i] is False:
stack.append(i)
visited[i] = True
DFS (Matrix)¶
DFS (Graph)¶
Backtracking¶
def backtrack(path, options):
# Base case: if the path is a complete solution
if is_solution(path):
results.append(path[:]) # Add a copy of the solution to results
return
for option in options:
if is_valid(option, path): # Check if the option is valid
path.append(option) # Make a choice
backtrack(path, options) # Explore further
path.pop() # Undo the choice (backtrack)