nhudinhtuan’s gists

nhudinhtuan / find_left_border.py

Last active June 9, 2021 16:40

Binary search - find the left border

	def find_left_border(arr, target):
	left = 0
	right = len(arr) - 1

	left_border = -1 # keep track of the latest smaller number
	while left <= right:
	mid = left + (right - left) // 2
	if arr[mid] < target:
	left_border = mid
	left = mid + 1

nhudinhtuan / find_right_border.py

Last active April 2, 2020 14:19

Binary search - find the right border

	def find_right_border(arr, target):
	left = 0
	right = len(arr) - 1

	right_border = -1 # keep track of the latest larger number
	while left <= right:
	mid = left + (right - left) // 2
	if arr[mid] <= target:
	left = mid + 1
	else:

nhudinhtuan / tree_traversal_inorder.py

Last active April 3, 2020 02:41

Tree traversal - Inorder

	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None

	# recursive version
	def inorder_traversal_recursive(root):
	result = []

nhudinhtuan / inorder_traversal_iterating.py

Last active April 2, 2020 07:49

Tree traversal - Inorder iterative implementation

	def inorder_traversal_iterating(root):
	result = []
	# using stack
	stack = []
	current = root
	while stack or current:
	if current:
	# traverse the left subtree
	stack.append(current)
	current = current.left

nhudinhtuan / tree_traversal_preorder.py

Last active April 3, 2020 02:44

Tree traversal - Preorder

	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None

	def preorder_traversal_recursive(root):
	result = []

	def recur(node):

nhudinhtuan / tree_traversal_preorder_interative.py

Last active April 2, 2020 07:49

Tree traversal - preorder

	def preorder_traversal_iterating(root):
	if not root:
	return []

	result = []
	# using stack
	stack = [root]
	while stack:
	current = stack.pop()
	# visit node

nhudinhtuan / tree_traversal_postorder.py

Last active April 3, 2020 02:49

Tree traversal - postorder

	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None

	def postorder_traversal_recursive(root):
	result = []

	def recur(node):

nhudinhtuan / tree_traversal_postorder_iterative.py

Last active April 2, 2020 07:49

Tree traversal - postorder

	def postorder_traversal_iterating(root):
	if not root:
	return []

	result = []
	stack = [root]
	# get the result in order of node, right, left
	while stack:
	current = stack.pop()
	if current.left:

nhudinhtuan / tree_traversal_levelorder.py

Last active April 3, 2020 02:53

Tree traversal - level order

	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None

	def levelorder_traversal_recursive(root):
	result = []

	def recur(node, level):

nhudinhtuan / tree_traversal_levelorder_iterative.py

Created April 2, 2020 07:50

Tree traversal - level order

	from collections import deque

	def levelorder_traversal_iterating(root):
	if not root:
	return []

	result = []
	# using queue
	queue = deque([root])
	while queue:

Naka Nhu nhudinhtuan