Traversal of a Binary-Tree

Posted on April 24, 2017 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Science, Computing Concepts

In this blog post we will investigate four key algorithms used to read through the content of a binary tree:

Breadth-First Traversal Algorithm
Depth-First Algorithms:
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal

Binary Tree?

A Binary Tree is a data structure used in some algorithms to store data. In a binary tree each node can have up to two children.

Breadth-First Traversal Algorithm

A Breadth-first traversal consists of accessing each node, one level after the other. On each layer the nodes are accessed as they appear, from left to right.

Depth-First Traversal Algorithms

There are three depth-first traversal agorithms which are all based on a recursive approach.

Pre-Order Traversal Algorithm:

FUNCTION preorder-traverse(tree)
    IF tree is not empty
         visit root node of tree
         preorder-traverse(left sub-tree)
         preorder-traverse(right sub-tree)
    END IF
END FUNCTION

FUNCTION preorder-traverse(tree)

IF tree is not empty

visit root node of tree

preorder-traverse(left sub-tree)

preorder-traverse(right sub-tree)

END IF

END FUNCTION

In-Order Traversal Algorithm:

FUNCTION inorder-traverse(tree)
    IF tree is not empty
         inorder-traverse(left sub-tree)
         visit root node of tree
         inorder-traverse(right sub-tree)
    END IF
END FUNCTION

FUNCTION inorder-traverse(tree)

IF tree is not empty

inorder-traverse(left sub-tree)

visit root node of tree

inorder-traverse(right sub-tree)

END IF

END FUNCTION

Post-Order Traversal Algorithm:

FUNCTION postorder-traverse(tree)
    IF tree is not empty
         postorder-traverse(left sub-tree)
         postorder-traverse(right sub-tree)
         visit root node of tree
    END IF
END FUNCTION