How do you transverse a binary tree? Discuss.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

The tree traversal is a way in which each node in the tree is visited exactly once in a symmetric manner.

The binary tree can be traverse in 3 ways:

  1. Pre-order traversal
  2. In-order traversal
  3. Post-order traversal

Pre-order Traversal

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This pre-order traversal is applicable for every root node of all subtrees in the tree.

Algorithm:

Until all nodes are traversed:-

Step 1: Visit root node

Step 2: Recursively traverse left sub-tree.

Step 3: Recursively traverse right sub-tree.

User Loaded Image | CSIT GuideE.g.

The preorder traversal output of the given above tree is: A B D H I E C F G

In-order Traversal:

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed recursively for all nodes in the tree

Algorithm:

Until all nodes are traversed:-

Step 1: Recursively traverse left sub-tree.

Step 2: Visit root node

Step 3: Recursively traverse right sub-tree.

E.g.

User Loaded Image | CSIT Guide

The inorder traversal output of the given tree is: H D I B E A F C G

Post-order Traversal

In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited.

Algorithm:

Until all nodes are traversed:-

Step 1: Recursively traverse left sub-tree.

Step 2: Recursively traverse right sub-tree.

Step 3: Visit root node

User Loaded Image | CSIT Guide

The post-order traversal output of the given above tree is: H I D E B F G C A

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .