Binary Tree PreOrder traversal in java

Previous
Next

If you want to practice data structure and algorithm programs, you can go through top 100+ data structure and algorithm interview questions.

This is 2nd part of java binary tree tutorial.

In this post, we will see about PreOrder binary tree traversal in java.

PreOrder traversal:

In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.
Steps for PreOrder traversal are:
  • Visit the node.
  • Traverse the left subtree in PreOrder.
  • Traverse the right subtree in PreOrder.

There can be two ways of implementing it

  • Recursive
  • Iterative

Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.


Code for recursion will be:

Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:

  1. Create empty stack and pust root node to it.
  2. Do the following when stack is not empty
    • Pop a node from stack and print it
    • Push right child of popped node to stack
    • Push left child of popped node to stack

We are pushing right child first, so it will be processed after left subtree as Stack is LIFO.

Example:
Lets say your binary tree is :

Lets create java program for PreOrder traversal:

Run above program and you will get following output:

Using Recursive solution:
40 20 10 30 60 50 70
————————-
Using Iterative solution:
40 20 10 30 60 50 70

Java Binary tree tutorial:

Please go through java interview programs for more such programs.
Previous
Next

Add Comment