Teaching Kids Programming – Binary Tree Traversal Algorithms (Preorder, Inorder, Reverse-Inorder, PostOrder and BFS)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Binary Tree, we can visit the nodes in a particular order – which is called Tree Traversal.

Example of a Complete Binary Tree

Binary Tree Pre-Order Traversal Algorithm

We visit the Node first then Recursively traverse the Left Tree and then Right Tree i.e. NLR.

def preOrder(root):
  if root is None:
    return
  print(root.val) # visit Node
  preOrder(root.left)
  preOrder(root.right)

The NLR of above tree is: 1,2,4,5,3,6

Binary Tree In-Order Traversal Algorithm

We recursively traverse the left tree, and then visit the node, and then traverse recursively the right tre i.e. LNR.

def inOrder(root):
  if root is None:
    return
  inOrder(root.left)
  print(root.val) # visit Node
  inOrder(root.right)

If we perform an inorder traversal to a Binary Search Tree, we will get a sorted list (in non-descending order).

For example:

  1
 / \
0   2
   / \
 1.5  3

Inorder traversal gives 0, 1, 1.5, 2, 3 which is in order.

Binary Tree Reverse In-Order Traversal Algorithm

The reverse in-order visits the nodes in RNL that is recursively traversing right tree, then visit node, then recursively traversing the left tree.

def ReverseInOrder(root):
  if root is None:
    return
  ReverseInOrder(root.right)
  print(root.val) # visit Node
  ReverseInOrder(root.left)

A Reverse In-order will print a sorted list in non-ascending order i.e. 3, 2, 1.5, 1, 0 (in above example).

Post Order Traversal Algorithm for Binary Tree

The post-order traversal visits the nodes in LRN order, which is recursively visiting left tree, then right tree, and visit the node last.

def postOrder(root):
  if root is None:
    return
  postOrder(root.left)
  postOrder(root.right)
  print(root.val) # visit Node

For above binary tree, the post-order traversal gives the order of: [0, 1.5, 3, 2, 1]

Breadth First Search Traversal

The Breadth First Search Traversal (BFS) is also one of the most important tree traversal algorithm. It traverses the binary tree in level-by-level order. For example, the above BFS traversal will give [0, 0, 2, 1.5, 3]. The implementation of a BFS is usually based on queue:

def bfs(root):
  if root is None:
    return
  q = [root]
  while len(q) > 0:
    p = q.pop(0)
    print(p.val) # visit node
    if p.left:
      q.append(p.left)
    if p.right:
      q.append(p.right)

All Binary Tree Traversal Algorithms run at O(N) time and O(N) space (due to recursion/stack or queue).

–EOF (The Ultimate Computing & Technology Blog) —