`Written by CCJ, Monday, Jan 18, 2021 @ Secaucus, NJ, USA.`

- CCJ’s Coding Note 2021 (1) - Basic Knowledge Points Summary
- DFS - Path Finding
- DFS - Cycle Finding
- Graph - Adjacency List Representation
- Heap and Heapify
- Binary Search
- Small Graph Knowledge Points:
- Small Python/C++ Knowledge Points
- 1) nonlocal
- 2) defaultdict
- 3) sorted
- 4) last index -1
- 5) DFS VS BFS
- 6) Python list
- 7) Queue: python list
- 8) Stack: python list
- 9) MAX and MIN number
- 10) Deque (Doubly Ended Queue)
- 11) print - end
- 12) bit shift
- 13) heap queue - heapq
- 14) ASCII Code - ord
- 15) reversed list
- 16) Binary Search in Python via bisect
- 17) C++ typedef
- 18) Logic Operators
- 19) Bitwise Operators in Python:
- 20) Bitwise Operators in C++:
- 21) C++11 Constexpr
- 22) Python isdigit()
- 23) How to Round Numbers in Python?

- Binary Tree Right Side View - DFS
- Binary Tree Right Side View - BFS

find a path between two given vertices

`u`

an`z`

;Use a stack

`S`

to keep track of the path between the start vertex and the current vertex

use a

`stack S`

to keep track of the path between the start vertex and the current vertexAs soon as a

`back`

edge (v, w) is encountered, we return the`cycle`

as the protion of the stack from the top to vertex 𝑤wShown as below:

Graph in Python can be implemented by

`defaultdict`

;DFS and BFS are implemented below;

```
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict
```
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
# Using List as defaultdict's default_factory
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A recursive function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited and print it
visited[v] = True
print(v, end = ' ')
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):
# Mark all the vertices as not visited
visited = [False] * (max(self.graph)+1)
# Call the recursive helper function to print DFS traversal
self.DFSUtil(v, visited)
# Function to print a BFS of graph
def BFS(self, s): # s is int value;
# Mark all the vertices as not visited
visited = [False] * (len(self.graph))
# Create a queue for BFS
queue = []
# Mark the source node as visited and enqueue it
queue.append(s)
visited[s] = True
while queue:
# Dequeue a vertex from queue and print it
# current vertex v:
# and the first value of v will be the starting node s;
v = queue.pop(0)
print (v, end = " ")
# Get all adjacent vertices of the
# dequeued vertex v. If an adjacent
# has not been visited, then mark it
# visited and enqueue it
for i in self.graph[v]: # for all incidentEdges(v), that is,edge (v, i)
if visited[i] == False:
queue.append(i)
visited[i] = True

A heap is a **binary tree** storing keys at **its internal nodes** and satisfying the following properties:

Heap-Order: for every internal node other than the root, key() key(parent()).

Complete Binary Tree: let be the height of the heap

for , there are nodes of depth ;

at depth , the internal nodes are to the left of the external nodes. By saying that all the internal nodes on level are

**“to the left”**of the external nodes, we mean that all the internal nodes on this level will be visited before any external nodes on this level in an inorder traversal.

The last node of a heap is the rightmost internal node of depth h − 1.

Method

`insertItem(k)`

: insert a key to the heap.