Difficulty: Easy; Category: Heap — What is Heap? Heap is a complete binary tree-based data structure. It can be divided into two types: Max-heap: the root node must be the greatest one, and all the parents are greater than their children. Min-heap: the root node must be the smallest one, and all the parents are…

Difficulty: Medium; Category: Dynamic Programming — Coin Change - LeetCode You are given an integer array coins representing coins of different denominations and an integer amount representing a…leetcode.com Creating a DP array mainly records the minimum number of coins for each amount. Take Example 1 as an example: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 The DP array would look like this:

Data Structures and Algorithms Note — Quick Sort and Merge Sort are Divide and Conquer algorithm Quick Sort Step pick a pivot (in this example will always pick the last element as a pivot) do partition then return the pivot index do quick sort for array before the pivot do quick sort for array after the pivot when…

Data Structures and Algorithms Note — Note: Depth First Traversal can be used to detect a cycle in a Graph Detect Cycle in a Directed Graph There are two situations the graph would be determined as having a cycle: A back edge is from a node to itself (self-loop) A node has an ancestor point to the node which is already been…

Data Structures and Algorithms Note — Breadth First Traversal The breadth first traversal will go through all vertices level by level. From [level 0] vertex 1 -> [level 1] vertex2, vertex3 -> [level 2] vertex 4, vertex 5 and finally [level 3] vertex6 We could use a queue to implement breadth first traversal, start from vertex1, then we append…

Data Structures and Algorithms Note — Create a balanced BST by input def insert(root, val): if not root: return Node(val) if root.val == val: return root elif root.val > val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root Get an array that uses inorder traversal for the tree def inorder(root, arr)…

Data Structures and Algorithms Note — What is Binary Search Tree nodes on the left subtree are all smaller than the node’s data nodes on the right subtree are all bigger than the node’s data the left and right subtree are also binary search tree Search a node Similar to binary search, if target data is smaller than current node data, go node.left, …

Data Structures and Algorithms Note — To identify whether tree 2 is a subtree of tree 1, first we need to consider how to compare whether two trees are the same. def sametree(self, t1, t2): # it is equal if tree both are None if t1 is None and t2 is None: return True …

Data Structures and Algorithms Note — Find the Height of the Tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None def height(node): #if tree from the node not exist, return 0 if node is None: return 0 # get the hight from the node's left tree and right tree l_height = height(node.left) r_height = height(node.right)