Binary Tree Traversals

O(n)
n = size(tree)

Python - DFS

	def preorder(root: TreeNode) -> None:
	if not root: return
	print(root.val)
	preorder(root.left)
	preorder(root.right)

view raw preorder.py hosted with ❤ by GitHub

	def inorder(root: TreeNode) -> None:
	if not root: return
	inorder(root.left)
	print(root.val)
	inorder(root.right)

view raw inorder.py hosted with ❤ by GitHub

	def postorder(root: TreeNode) -> None:
	if not root: return
	postorder(root.left)
	postorder(root.right)
	print(root.val)

view raw postorder.py hosted with ❤ by GitHub

Java - DFS

	void preorder(TreeNode root) {
	if (root == null) return;
	System.out.print(root.val + " ");
	preorder(root.left);
	preorder(root.right);
	}

view raw Preorder.java hosted with ❤ by GitHub

	void inorder(TreeNode root) {
	if (root == null) return;
	inorder(root.left);
	System.out.print(root.val + " ");
	inorder(root.right);
	}

view raw Inorder.java hosted with ❤ by GitHub

	void postorder(TreeNode root) {
	if (root == null) return;
	postorder(root.left);
	postorder(root.right);
	System.out.print(root.val + " ");
	}

view raw Postorder.java hosted with ❤ by GitHub

Python - BFS | Java - BFS

	def levelorder(root: TreeNode) -> None:
	if not root: return
	q = deque([root])
	while q:
	size = len(q)
	for i in range(size):
	node = q.popleft()
	print(str(node.val), end = " ")
	if node.left:
	q.append(node.left)
	if node.right:
	q.append(node.right)
	print()

view raw levelorder.py hosted with ❤ by GitHub

	void levelorder(TreeNode root) {
	if (root == null) return;
	Deque<TreeNode> q = new ArrayDeque<>();
	q.addLast(root);
	while (q.isEmpty() == false) {
	int size = q.size();
	for (int i = 0; i < size; i++) {
	TreeNode node = q.removeFirst();
	System.out.println(node.val + " ");
	if (node.left != null) q.addLast(node.left);
	if (node.right != null) q.addLast(node.right);
	}
	System.out.println();
	}
	}

view raw levelorder.java hosted with ❤ by GitHub

Tricks

Inorder Traversal of a Binary Search Tree