Binary Tree Traversal

Traversing a tree means that we will visit each node in a specific order. There are three ways to implement:

• Inorder
• Preorder
• Postorder

For each of these, it is assumed that the trees being traversed are not empty. To implement each of the traversals you can follow the algorithms below.

Inorder Traversal Algorithm

inOrder(root)

if (root != null) then
    inOrder(root.leftNode)
    output root.value
    inOrder(root.rightNode)
end if

PreOrder Traversal Algorithm

preOrder(root)

if (root != null) then 
    output root.value
    preOrder(root.leftNode)
    preOrder(root.rightNode)
end if

PostOrder Traversal Algorithm

postOrder(root)

if (root != null) then
    postOrder(root.leftNode)
    postOrder(rood.rightNode)
    output root.value
end if

Traversal is useful for examinations and has a few real-world use cases –

In Order Traversal: This is useful for any tree and it returns the order of the nodes from the lowest value to the greatest value.

Preorder Traversal: This is useful for any tree and it lets you create a copy of the tree.

Postorder Traversal: This lets you delete a tree safely. The lowest level is accessed first, followed by the next level and so on until you get to the root.

Let’s look at some examples: