# Binary Tree Traversal Cheat Sheet

Traversing binary trees is a fundamental skill required for coding interviews. Today I will teach you the main ways of traversing a binary tree. Each traversal style is associated with a specific pattern. Below is a quick reference. (All code examples are worked in python)

# Binary Tree Traversal Cheat Sheet

Traversal->PatternIn-order left/center/rightpre-order center/left/rightpost-order left/right/centerlevel-order left to right

In-order -> Left/Center/Right

Pre-order -> Center/Left/Right

Post-order -> left/right/center

Level-order -> left to right

# Example

## Pre-Order Traversal

A preorder traversal follows the center-left-right pattern. For the tree above, the output would be [0,1,2,6,4,5,7,8,3]

**Solution:**

**def** **preOrderHelper**(tree, array **=** []):

**if** tree **!=** None:

array.append(tree.value)

preOrderHelper(tree.left,array)

preOrderHelper(tree.right,array)

**return** array

## In-Order Traversal

An inorder traversal follows the left-center-right pattern. The algorithm will traverse as far left as possible and then add each center node with the right node being added last. An in-order traversal of the graph above would output [2,1,4,6,5,0,7,8,3]

**Solution:**

**def** **inOrder**(tree, array **=** []):

**if** tree **!=** None:

inOrderHelper(tree.left,array)

array.append(tree.value)

inOrderHelper(tree.right,array)

**return** array

## Post-Order Traversal

A postorder traversal follows the left-right-center pattern. For the tree above the output would be [2,4,5,6,1,8,3,7,0].

**Solution:**

**def** **postOrder**(tree, array **=** []):

**if** tree **!=** None:

postOrderHelper(tree.left,array)

postOrderHelper(tree.right,array)

array.append(tree.value)

## Level Order Traversal

A level order traversal will return a two dimensional list of every level in the tree. For the example above, the result would be:

[[0], [1,7], [2,6,8,3], [4,5]]

The code below uses a helper function. The helper function keeps track of which level of the tree it is located in.

**Solution:**

**def** **levelOrder**(root: TreeNode) **->** List[List[int]]:

**if** root **==** None:

**return** [[]]

acc **=** [[]]

helper(root,acc,0)

**return** acc

**def** **helper**(root,acc,ind):

**if** root **==** None:

**return** acc

**else**:

**if** len(acc) **<** ind **+** 1:

acc.append([])

acc[ind].append(root.val)

helper(root.left,acc,ind **+** 1)

helper(root.right,acc,ind **+** 1)

**return** acc