Tree Traversals – Inorder, Preorder, Postorder

You are currently viewing Tree Traversals – Inorder, Preorder, Postorder
Tree Traversals - Inorder, Preorder and Postorder

Tree traversal is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. Tree traversal is also known as tree search and walking the tree.

Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node. As a tree is a self-referential (recursively defined) data structure, traversal can be defined by recursion or, more subtly, co-recursion, in a very natural and clear fashion; in these cases the deferred nodes are stored implicitly in the call stack.
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue, including co-recursively.

We will use Java programming language here for illustration purpose.

Pre-order (Current -> Left -> Right)

The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done. Every node represents a subtree itself.

  • Access the data part of the current node.
  • Traverse the left subtree by recursively
  • Traverse the right subtree by recursively
// preOrder traversal - Recursive version Root, Left, Right
	public void preorderTraversal(Node root) {
		if (root == null)
			return;
		processNode(root);
		preorderTraversal(root.getLeftChild());
		preorderTraversal(root.getRightChild());
	}

In-order (Left -> Node -> Right)

  • Traverse the left subtree by recursively calling the in-order function.
  • Access the data part of the current node.
  • Traverse the right subtree by recursively calling the in-order function.

In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.

	public void inorderTraversal(Node root) {
		if (root == null)
			return;
		inorderTraversal(root.getLeftChild());
		processNode(root);
		inorderTraversal(root.getRightChild());
	}

Post-order (Left -> Right -> Node)

  • Traverse the left subtree by recursively calling the post-order function.
  • Traverse the right subtree by recursively calling the post-order function.
  • Access the data part of the current node.
	public void postorderTraversal(Node root) {
		if (root == null)
			return;
		postorderTraversal(root.getLeftChild());
		postorderTraversal(root.getRightChild());
		processNode(root);
	}

In Above example Node is the customer Object (Binary tree representation) which contains data, reference to left child and reference to right node.

Here is the full Java program, in case you want to have a working example:

public class TreeTraversals {

	Node root;

	public TreeTraversals() {
		root = null;
	}

	public Node createTree() {
		if (root == null) {
			root = new Node(12);
		}
		root.setLeftChild(new Node(23));
		root.setRightChild(new Node(18));
		root.getLeftChild().setLeftChild(new Node(11));
		root.getLeftChild().setRightChild(new Node(43));
		root.getRightChild().setLeftChild(new Node(19));
		root.getRightChild().setRightChild(new Node(50));
		return root;
	}

	/*
	 * preOrder traversal - Recursive version Root, Left, Right
	 */
	public void preorderTraversal(Node root) {
		if (root == null) {
			return;
		}
		/* Append node data in string buffer */
		processNode(root);
		preorderTraversal(root.getLeftChild());
		preorderTraversal(root.getRightChild());
	}

	/*
	 * inOrder traversal - Recursive version Left, Root, Right
	 */
	public void inorderTraversal(Node root) {
		if (root == null) {
			return;
		}
		inorderTraversal(root.getLeftChild());
		processNode(root);
		inorderTraversal(root.getRightChild());
	}

	/*
	 * postOrder traversal - Recursive version Left, Right, Root
	 */
	public void postorderTraversal(Node root) {
		if (root == null) {
			return;
		}
		postorderTraversal(root.getLeftChild());
		postorderTraversal(root.getRightChild());
		processNode(root);
	}

		private void processNode(Node root) {
		System.out.print(root.getData() + " ");
	}

	public static void main(String[] args) {
		TreeTraversals bt = new TreeTraversals();
		Node root = bt.createTree();
		System.out.println("\n1. Pre order traversal:\t");
		bt.preorderTraversal(root);

		System.out.println("\n2. In order traversal: \t");
		bt.inorderTraversal(root);

		System.out.println("\n3. Post order traversal:\t");
		bt.postorderTraversal(root);
	}

	class Node {

		private int data;
		private Node leftChild;
		private Node rightChild;

		public Node(int data) {
			this.data = data;
			leftChild = null;
			rightChild = null;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public Node getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}

		public Node getRightChild() {
			return rightChild;
		}

		public void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}
	}
}

References:

https://en.wikipedia.org/wiki/Tree_traversal