Binary Tree in C++ – 3 : Traversals

We look at 3 standard ways to traverse the nodes of a binary.

1. Preorder traversal

2. Postorder traversal

3 . Inorder traversal

——

1. Preorder traversal – A node pointer to the root of the tree (or subtree) to be traversed is passed to the function.

in this, we traverse the root first, before traversing the left subtree and the right subtree. Each subtree is in turn traversed in a preorder fashion. This results in a sequence of traversal wherein the parent is always traversed before either of its children.

——–

void preorder ( Node* root)

{

if ( root == (Node*) NULL)

return;

 

cout << root -> data << endl;

preorder (root -> left_ptr);

preorder (root -> right -> ptr);

}

———

Preorder traversal on a tree having n nodes takes O(n) time.

——

2. Postorder traversal – here, the root is traversed after the left and right subtrees have been traversed.

—-

void postorder ( Node* root)

{

if ( root == (Node*) NULL)

return;

postorder ( root -> left_ptr);

postorder (root -> right_ptr);

cout << root -> data << endl;

}

——-

Postorder traversal takes O(n) time.

—–

3. Inorder traversal – here, the order of traversal is the left subtree followed by the root followed by the right subtree.

——

void inorder ( Node *root)

{

if ( root == (Node*) NULL)

return;

inorder (root -> left_ptr);

cout << root -> data << endl;

inorder (root -> right_ptr);

}

——

Inorder traversal also takes O(n) time.

——-


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: