Preorder Tree Traversal (DFS) in java

Posted on Updated on

Traversing of tree has different approach than that of linear data structures (Array, Linked List, Queues, Stacks, etc).

There are different ways to traversal a tree in DFS such as:

  1. Preorder
  2. Inorder
  3. Postorder

Here in this article, we shall discuss steps and different approach of implementing Preorder tree traversal.

Steps for Preorder Tree Traversal are :

1) Visit the root.
2) Traverse the left subtree, i.e., call Preorder(left-subtree)
3) Traverse the right subtree, i.e., call Preorder(right-subtree)                                                 Tree
Preorder Traversal of above tree is 10, 20, 40, 70, 50, 30, 60

Time Complexity: O(n)

There are two ways to implement Preorder Tree Traversal.

1) Recursive
2) Iterative

Recursive solution for Preorder Tree Traversal :

Recursive solution for Preorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is

Code for recursive solution

Output

Iterative solution for Preorder Traversal

To implement iterative solution for preorder Traversal, we will be using Stack data structure.Algorithm for iterative solution is

Code for iterative solution

Output

Download code for Preorder Tree Traversal

PreorderTraversal

Stay tuned for more updates and tutorials !!!

Leave a Reply

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

Time limit is exhausted. Please reload CAPTCHA.