Given a binary tree, return the inorder traversal of its nodes’ values.

For traversing a binary tree in in-order fashion, we must do these three things for every node N starting from root node of the tree:
(L) Recursively traverse its left subtree. When this step is finished we are back at N again.
(N) Process N itself
(R) Recursively traverse its right subtree. When this step is finished we are back at N again.

In normal in-order traversal we visit left subtree before the right subtree. If we visit right subtree before visiting the left subtree, it is referred as reverse in-order traversal.

Example:
Input: 1 / \ 2 3 / \ 4 5 Output: Inorder (Left, Root, Right) : 4 2 5 1 3

As we can see before processing any node, the left subtree is processed first, followed by the node and the right subtree is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as depth-first search(DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

Solution

We can use recurrsion to traverse InOrder.

1. Traverse Left Node. 2. Process Current Node. 3. Traverse Right Node.
Code

Output

4 2 5 1 3

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *