Binary Tree PreOrder Traversal in Java

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

1. Introduction

In this article, we will explore the concept of InOrder traversal in binary trees, focusing on its implementation in Java. In computer science, a binary tree is a foundational data structure, and traversing it is a fundamental technique. Among the various traversal methods, PreOrder traversal is widely used due to its applications across a range of algorithms and operations.

2. What is PreOrder Traversal?

In PreOrder traversal,each node is processed before either of its sub-trees. In simpler words, visit each node before its children.

3. Process of PreOrder Traversal

  • Visit the node.
  • Traverse the left subtree in PreOrder.
  • Traverse the right subtree in PreOrder.

4. Implementation

There can be two ways of implementing it:

  • Recursive
  • Iterative

4.1 Recursive Solution

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

Code for recursion will be:

The time complexity for recursive approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.

The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of the call stack to handle recursion. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).

4.2 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:

  • Create empty stack and pust root node to it.
  • 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.

The time complexity for iterative approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.

The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of an explicit stack to keep track of nodes. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).

5. Complete Java Program

Let’s say our binary tree is:

Binary tree

Here is complete 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

6. Conclusion

In this article, we covered about Binary tree PreOrder traversal and its implementation. We have done traversal using two approaches: Iterative and Recursive. We also discussed about time and space complexity for the PreOrder traversal.

Java Binary tree tutorial:

Please go through java interview programs for more such programs.

Was this post helpful?

Leave a Reply

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