Pre Order Traversal

Pre- Order Traversal and its Algorithm

By

Junaid Ali Siddiqui

Data s tr uct ur e A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data. Often a carefully chosen

Data structure

Linear data structure

Non linear data structure

What is l in ear a nd n onli near data st ructures?  Linear data structure  A data structure is said to be linear if the elements form a sequence for example Array Linked list queue etc.  Non linear data structure  Elements in a nonlinear data structure do not form a sequence for example Tree Hash tree Binary tree etc.

Bin ary tr ee  In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right.

Typ es of b inary trees  Complete binary tree  A binary tree is said to be complete binary tree if all its nodes has exactly two Except the leave or terminal nodes, which Have no child at all.

Ex tended b in ary tree  A binary tree is said to be extended s binary tree,if all its nodes has exactly either two children or no child at all

Tr ave rsin g a tr ee  tree-traversal refers to the process of visiting (examining and/or updating) each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.

pre-o rder trave rsin g  Its is one of the most important and popular method of tree traversal. The steps involved in pre order traversal are as following. 1)Access the parent node 2)Access the left most child of parent node. 3)Access the right child of parent node.

 Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)

Tr aver sa l alg or ith m PREORD(INFO,LEFT,RIGHT,ROOT) A binary tree T is in memory .the algorithm does a preorder traversal of T, Applying an operation PROCESS to each of its nodes. An array stack is used to temporarily hold the address of nodes.

1)[initially push NULL onto STACK, and initialize PTR] Set TOP=1,STACK[1]=NULL and PTR=ROOT

2) Repeat step 3 to 5 while PTR != NULL 3)Apply PROCESS to INFO[PTR] 4)[right child?] If RIGHT[PTR]!= NULL, then :[push on STACK.] Set TOP=TOP+1 ,and STACK [TOP]=RIGHT[PTR] [End of If structure]

1) [Left child?] If LEFT[PTR] != LEFT[PTR], Else : [pop from STACK] Set PTR =STACK[TOP] and TOP =TOP-1 [end of If structure] [End of step 2 loop] 6) EXIT

THE END