Preorder tree Traversal using Recursion in Java

Hey coders! There are multiple ways to traverse a tree in Java. In this tutorial, we will learn one of the three ways of DFS ( depth-first search ) that is Preorder tree Traversal with Recursion in Java, as recursion is the simplest way to solve tree based problems. It is also known as NLR (node left right) algorithm.

To traverse a tree in Preorder fashion there are three steps:

  • Process the parent node
  • Recursively traverse left child
  • Recursively traverse right child

Note: If we traverse the right child before the left child then such a traversal is called Reverse preorder traversal.

Preorder tree Traversal using Recursion in Java

In the example above we can see that only after processing the node the left subtree is recursively processed followed by the right subtree.

To implement this in code we create a data structure to store a Binary Tree Node and then we write a function to create a new binary tree node having given value.

class Node
{
  int data;
  Node left, right;
  public Node(int value)
  {
    data = value;
    left = right = null;
  }
};

Code for Preorder Traversal with recursion in Java

class Node
{
  int data;
  Node left, right;
  public Node(int value)
  {
    data = value;
    left = right = null;
  }
};

class PreorderTraversal
{
  public static void preorder(Node root)
  {
    if (root == null) {
      return;
    }
    
    System.out.print(root.data + " ");
    preorder(root.left);
    preorder(root.right);
  }

  public static void main(String[] args)
  {	
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.right.left.left = new Node(8);
    root.right.left.right = new Node(9);

    System.out.print("The preorder traversal for the tree is: ");
    preorder(root);
  }
}

Output:

The preorder traversal for the tree is: 1 2 4 5 3 6 8 9 7

Explanation of Java program of Preorder tree Traversal using Recursion

  • Firstly we construct the tree and use the recursive function to perform Preorder traversal of the tree.

    The Constructed tree is:

 1
/    \
/        \
2           3
/ \           / \
/      \      /     \
4       5    6       7
/ \
/      \
8        9

  • If the current node is not empty :
    1. Display the parent node.
    2. Traverse the left subtree and display the node.
    3. Traverse the right subtree and display the node.

Hope you’ve understood the code 🙂
Any questions please feel free to drop in your comments.

You can also read:

Leave a Reply

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