Why tree traversal

Just as a linked list is composed of a collection of link objects, a tree is composed of a collection of node objects. This class will be used by some of the binary tree structures presented later.

Member functions are provided that set or return the element value, return a pointer to the left child, return a pointer to the right child, or indicate whether the node is a leaf.

A traversal routine is naturally written as a recursive function. Its input parameter is a pointer to a node which we will call rt because each node can be viewed as the root of a some subtree. The initial call to the traversal function passes in a pointer to the root node of the tree. The traversal function visits rt and its children if any in the desired order.

For example, a preorder traversal specifies that rt be visited before its children. This can easily be implemented as follows. Function preorder first checks that the tree is not empty if it is, then the traversal is done and preorder simply returns. Otherwise, preorder makes a call to visit , which processes the root node i. Function preorder is then called recursively on the left subtree, which will visit all nodes in that subtree.

Finally, preorder is called on the right subtree, visiting all nodes in the right subtree. Postorder and inorder traversals are similar. B is also traversed post-order. To check the C implementation of tree traversing, please click here. Previous Page. Next Page.

Previous Page Print Page. Save Close. Dashboard Logout. Interview Questions. Company Questions. Artificial Intelligence. Cloud Computing. Data Science. Angular 7. Machine Learning. Data Structures. Operating System.

Computer Network. Compiler Design. Computer Organization. Discrete Mathematics. Ethical Hacking. Computer Graphics.

Software Engineering. Web Technology. Cyber Security. C Programming. Control System. Data Mining. Data Warehouse.

Javatpoint Services JavaTpoint offers too many high quality services. The following are the three different ways of traversal: Inorder traversal Preorder traversal Postorder traversal Let's look at each traversal one by one. Inorder Traversal An inorder traversal is a traversal technique that follows the policy, i. Let's understand the inorder traversal through an example. Consider the below tree for the inorder traversal. As node B does not have any left child so B will be printed as shown below: After visiting node B, we move to the right child of node B, i.

Since node D is a leaf node, so node D gets printed as shown below: The left part of node A is traversed. Since G is a leaf node, so G gets printed as shown below: The root node of G is E, so it gets printed as shown below: Since E does not have any right child, so we move to the root of the E node, i. C gets printed as shown below: Once the left part of node C and the root node, i. Since H is a leaf node, so it gets printed as shown below: Now we move to the root node of H, i.

Preorder Traversal A preorder traversal is a traversal technique that follows the policy, i. Let's understand the Preorder traversal through an example. Consider the below tree for the Preorder traversal. As node A is the root node in the above tree, so it gets printed as shown below: Once the root node is traversed, we move to the left subtree. Therefore, B gets printed as shown below: Since node B does not have a left child, and it has only a right child; therefore, D gets printed as shown below: Once the left part of the root node A is traversed, we move to the right part of node A.