Data Structure Tree Traversal with Examples

 

 

 

DATA STRUCTURE

Trees and Tree Traversal

 

 

Tree

Trees are hierarchical data structures.

Linked Lists, Stack and queues are linear data structures

 Tree: The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. Finally, elements with no children are called leaves. 

Trees provide moderate access/search quicker than Linked List and slower than arrays. 
Trees provide moderate insertion/deletion quicker than Arrays and slower than Unordered Linked Lists. 

Binary Tree: A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 

The following are common types of Binary Trees. 

Full Binary Tree A Binary Tree is a full binary tree if every node has 0 or 2 children. The following are the examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaf nodes have two children. 

 

Complete Binary Tree: A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible 

The following are examples of Complete Binary Trees 

 

 

 

 

Perfect Binary Tree A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level. 
The following are the examples of Perfect Binary Trees. 

Tree Traversal

 

Traversal is a process to visit all the nodes of a tree. There are three ways which we use to traverse a tree

• In-order Traversal
• Pre-order Traversal
• Post-order Traversal

 

 

In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.

Step 2 − Visit root node.

Step 3 − Recursively traverse right subtree.

 

D → B → E → A → F → C → G

 

We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be −

 

 

In-order Traversal Example

8,4,2,5,1,9,6,10,3,7

 

Pre-order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.

Step 2 − Recursively traverse left subtree.

Step 3 − Recursively traverse right subtree.

 

 

A → B → D → E → C → F → G

 

We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be −

 

Pre-order Traversal Example

1,2,4,8,5,3,6,9,10,7

 

 Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.

Step 2 − Recursively traverse right subtree.

Step 3 − Visit root node.

 

D → E → B → F → G → C → A

 

We start from A, and following Post-order traversal, we first visit the left subtree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be −

 

Post-order Traversal Example

8,4,5,2,9,10,6,7,3,1

 Level order Traversal

1,2,3,4,5,6,7,8,9,10

 

Example :2 Find Preorder , Inorder , Postorder  

 

   

Preorder   : 8,5,9,7,1,12,2,4,11,3                

Inorder     : 9,5,1,7,2,12,8,4,3,11              

Postorder : 9,1,2,12,7,5,3,11,4,8

 

       

 Preorder                  Inorder                     Postorder