Binary Tree Traversal in Java, easy in 5 minutes

This post shows you about Binary Tree Traversal in Java programming language. Using inorder, preorder and postorder algorithm to traverse a tree means visiting every node in the tree. Not like linear data structures (arrays, stacks, queues, linked list) have only one way to visit. But a hierarchical data structure like a tree can be traversed in some ways.

 

Binary Tree Traversal in Java

Binary Tree Traversal in Java

Three ways of traversal (Depth First Traversals)

Inorder traversal  algorithm

  1. First, visit all the nodes in the left subtree
  2. Then visit the root node
  3. Visit all the nodes in the right subtree
    Inorder traversal

Following the order from 1 to 4 in the above image, you have the list of nodes: 40, 20, 50, 10, 30

Application of Inorder Traversal: If a tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, then an Inorder traversal should be used. The tree would be flattened in the same way it was created.

Preorder Traversal algorithm

  1. Visit root node
  2. Traversal all the nodes in the left subtree
  3. Traversal all the nodes in the right subtree

Preorder Traversal

Following the order from 1 to 4 in the above image, you have the list of nodes: 10, 20, 40, 50, 30

Application of Preorder Traversal: If you need to explore the roots before inspecting any leaves, you pick Preorder because you will encounter all the roots before all of the leaves.

Postorder Traversal algorithm

  1. Traversal all the nodes in the left subtree
  2. Traversal all the nodes in the right subtree
  3. Visit the root node

Postorder Traversal

Following the order from 1 to 4 in the above image, you have the list of nodes: 40, 50, 20, 30, 10.

Application of Postorder Traversal: If you need to explore all the leaves before any nodes, you select

Postorder because you don’t waste any time inspecting roots in search for leaves.

Implement a Binary Tree Traversal in Java

Here is a simple java program that demos three ways to visit a tree.

Running the above program, you get the output like this:

Binary Tree Traversal in Java

Time Complexity

Because you traverse each node once in a binary tree with n nodes. While the amount of work you do for each node is constant (does not depend on the rest of the nodes). So time complexity is O(n)

That’s all about Binary Tree Traversal in Java.

References

Binary Tree Data Structure in Java
Binary Tree Java Documentation

Please share it if you found this useful
Hide Buttons