Selected Writings

Intro

# Definition for a binary tree node
# and type hint imports
from Typing import List, Tuple
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

• Leetcode problem #144, #94, #145, #102 are covered, i.e., Pre-order, In-order, Post-order, Level-order, respectively.
• The recursive solution and colorize label solution are quite intuitive. Consider them as a template for Binary Tree Traversal Problem.
• For vanilla iterative solution, Pre-order and In-order is pretty much similar while Post-order has some differences that mainly focus on marking previously visited node and doing some conditional statements.
• Recurive solution for Level-order problem is not provided and colorize label solution is not applicable.

Solutions

Recurisve

def traversal(root: TreeNode) -> List[int]:
	ans: List[int] = []
	def dfs(root):
		if not root:
			return
		# Pre-order
		ans.append(root.val)
		dfs(root.left)
		dfs(root.right)
	return ans

def traversal(root: TreeNode) -> List[int]:
	ans: List[int] = []
	def dfs(root):
		if not root:
			return
		# In-order
		dfs(root.left)
		ans.append(root.val)
		dfs(root.right)
	return ans

def traversal(root: TreeNode) -> List[int]:
	ans: List[int] = []
	def dfs(root):
		if not root:
			return
		# Post-order
		dfs(root.left)
		dfs(root.right)
		ans.append(root.val)
	return ans

Iterative

Colorize Label Solution

<aside> 💡 Note that this solution is a simulation of recursive stack call, the runtime performance is relatively similar to recursive solution and slower than vanilla iterative solution.

</aside>

def traversal(root: TreeNode) -> List:
	WHITE, RED = 0, 1
	ans: List[int] = []
	if not root:
		return ans
	stack: List[Tuple[int, TreeNode]] = [(WHITE, root)]
	while stack or root:
		color, tmp = stack.pop()
		if not tmp:
			continue;
		if color == WHITE:
			# Pre-order, notice the append order is reversed
			stack.append((WHITE, tmp.right))
			stack.append((WHITE, tmp.left))
			stack.append((RED, tmp))
		else:
			ans.append(tmp.val)
	return ans

def traversal(root: TreeNode) -> List:
	WHITE, RED = 0, 1
	ans: List[int] = []
	if not root:
		return ans
	stack: List[Tuple[int, TreeNode]] = [(WHITE, root)]
	while stack or root:
		color, tmp = stack.pop()
		if not tmp:
			continue;
		if color == WHITE:
			# In-order, notice the append order is reversed
			stack.append((WHITE, tmp.right))
			stack.append((RED, tmp))
			stack.append((WHITE, tmp.left))
		else:
			ans.append(tmp.val)
	return ans

def traversal(root: TreeNode) -> List:
	WHITE, RED = 0, 1
	ans: List[int] = []
	if not root:
		return ans
	stack: List[Tuple[int, TreeNode]] = [(WHITE, root)]
	while stack or root:
		color, tmp = stack.pop()
		if not tmp:
			continue;
		if color == WHITE:
			# Post-order, notice the append order is reversed
			stack.append((RED, tmp))			
			stack.append((WHITE, tmp.right))
			stack.append((WHITE, tmp.left))
		else:
			ans.append(tmp.val)
	return ans

Vanilla Solution

def traversal(root: TreeNode) -> List:
	ans: List[int] = []
	if not root:
		return ans
	stack: List[TreeNode] = []
	while stack or root:
		while root:
			# Pre-order, insert root val first
			ans.append(root.val)
			stack.append(root)
			root: Optional[TreeNode] = root.left
		tmp: TreeNode = stack.pop()	
		root: Optional[TreeNode] = tmp.right
	return ans

def traversal(root: TreeNode) -> List:
	ans: List[int] = []
	if not root:
		return ans
	stack: List[TreeNode] = []
	while stack or root:
		while root:
			stack.append(root)
			root: Optional[TreeNode] = root.left
		tmp: TreeNode = stack.pop()
		# In-order, insert left node val first
		ans.append(tmp.val)
		root: Optional[TreeNode] = tmp.right
	return ans

def traversal(root: TreeNode) -> List:
	ans: List[int] = []
	if not root:
		return ans
	stack: List[TreeNode] = []
	# Post-order
	prev: Optional[TreeNode] = None
	while stack or root:
		while root:
			stack.append(root)
			root: Optional[TreeNode] = root.left
		tmp: TreeNode = stack.pop()
		# Post-order
		# insert tmp val when tmp has no right child or
		# tmp.right is visited previously
		if not tmp.right or tmp.right == prev:
			ans.append(tmp.val)
			prev = tmp
			root = None
		else:
			# if not, it means that cur still has right child
			# that needs to be visited, so append it to stack
			stack.append(tmp)
			root: Optional[TreeNode] = tmp.right
	return ans

def levelOrder(self, root: TreeNode) -> List[List[int]]:
	ans: List[List[int]] = []
	if not root:
		return ans
	stack: List[Tuple(int, TreeNode)] = [(0, root)]
  while stack:
	  level, tmp = stack.pop()
    if len(ans) <= level:
	    ans.append([])
    ans[level].append(tmp.val)
    if tmp.right:
	    stack.append((level + 1, tmp.right))
		if tmp.left:
			stack.append((level + 1, tmp.left))
	return ans