Preorder Traversal in a Binary Tree

Preorder Traversal in a binary tree defines that the root node of a tree/ subtree is visited before its left and right child nodes. It can be defined as Root-Left-Right. This Traversal process in Binary Trees can be done by recursive and non recursive methods.

Recursive Preorder Traversal

In recursive traversal the address of current node is stored in a pointer CURR. CURR pointer is initialized to the Root of the binary tree.

In all the subsequent recursive calls the CURR->LEFT or CURR->RIGHT nodes are passed as the last argument. The node passed as last argument becomes the root for the subtree that is currently being traversed.

The traversal procedure is repeatedly called for left and right child nodes till CURR (pointer storing address of current node) becomes NULL.

Algorithm REC_TRAVERSAL(DATA, LEFT, RIGHT, ROOT)
1.	[ Initialize Pointer]  CURR=ROOT
2.	IF CURR <>NULL
      a.	Process node CURR
      b.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->LEFT)
      c.	REC_TRAVERSAL (DATA, LEFT, RIGHT, CURR->RIGHT)
3.	Exit

Non-Recursive Traversal

In non-recursive Traversal an intermediary storage data structure Stack is used to maintain the nodes that are still to be traversed.

Traversal begins from the root node. The current node is processed and right child node of the current node is preserved in the stack to be processed while backtracking from leaf node. Once a leaf node is reached, backtracking is used to pick up the unvisited node and performing the similar traversal operation.

Algorithm NONREC_TRAVERSAL (DATA, LEFT, RIGHT, ROOT)
1.	[Initialize variables and stack] TOS=1, STK[TOP]=# , CURR=ROOT
2.	[Follow the leftmost  branch of the tree while saving right child nodes in stack and 
         popping node  from stack  for backtracking]
        Repeat steps 3, 4 and 5 while CURR<> NULL
3.	Print DATA[CURR]
4.	[If Right child node is existing for current node store it in the stack]
        TOS=TOS+1
        STK[TOS]=CURR->RIGHT
5.	[If Left child node is existing for current node make the Left child as the current 
        node else pop topmost node from stack to backtrack]
        If CURR->LEFT<>NULL
	    CURR= CURR->LEFT
        Else
            CURR= STK[TOS]
            TOS=TOS-1
6.	END

Preorder Traversal of Arithmetic Expression Tree

One immensely useful application of Preorder Traversal is converting an arithmetic expression stored in a binary tree into prefix notation. Prefix notation is also called Polish Notation wherein a Binary Operator precedes the operands that it operates on.

Consider the following expression-

A+B

Its Prefix Notation or Polish Notation is +AB.

When an arithmetic binary expression is represented in an expression tree, Traversal of such an expression tree in Preorder will result in its corresponding Prefix expression.

The following image shows an expression tree made from the binary expression (a+b)*(c-d)