Given a binary tree, return the pre-order traversal of its nodes’ values.

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

In normal pre-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 pre-order traversal.

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

As we can see before processing any node, the left subtree is processed first, followed by the right subtree. 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 PreOrder.

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

Output

1 2 4 5 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 *