Write a java program to traverse a binary tree using preorder traversal

We have to write a java program to traverse a binary tree using preorder traversal. For this, let us first understand the terms binary tree and preorder traversal.

What is a binary tree?

  • A binary tree is a non-primitive data structure that holds the values in a tree-like fashion.
  • The tree has a parent-child relationship.
  • It is made up of nodes that hold the data.
  • The top node of the tree is called the root.
  • In binary tree, each node can have 0, 1, or 2 children ( also known as subnodes ).
  • All the left subnodes hold the data lesser than the parent node and all the right subnodes hold the data greater than the parent node. The below diagram shows one such binary tree.

What is preorder traversal?

Traversal means accessing each node usually with an intention to print the data.

Preorder traversal is the tree traversal that prints the data in the following manner:

  1. first the root node
  2. then the left subnode
  3. then the right subnode

Example:

Output:

The preorder traversal for the binary tree is:

33->21->8->25->45->42->50

Write an algorithm to traverse a binary tree using preorder traversal:

  1. First, create a class Node that represents a node of the binary tree. The Node class has three attributesĀ  – data, left subnode, and right subnode. Create a parameterized constructor of the Node class that initializes the data attribute by the argument passed and left and right subnodes by null.
  2. Next, create a BinaryTree class that has the main method. Declare a root variable of the node type and initialize it by null.
  3. Create a function named preorder() that traverses our binary tree in a preorder manner. It takes a node as an argument. This function is a recursive function that runs until the whole tree is traversed.
  4. The exit condition of this preorder() function is that if the node becomes equals to null, it will return from the function.
  5. As we are performing the preorder traversal, first print the value of the root node ( using node.data )
  6. Next, call the preorder() function for the left subnode and then for the right subnode.
  7. We have thus traversed the binary tree using preorder traversal.

Write a program to traverse a binary tree using preorder traversal:

class Node
{
    int data;
    Node left, right;
    Node(int data)
    {
        this.data=data;
        left=right=null;
    }
}
public class BinaryTree 
{
    Node root=null;
    public void preorder(Node node)
    {
        if(node==null) return;
        System.out.print(node.data+" ");
        preorder(node.left);
        preorder(node.right);
    }
    public static void main(String[] args) 
    {
        BinaryTree bt=new BinaryTree();
        bt.root=new Node(33);
        bt.root.left=new Node(21);
        bt.root.right=new Node(45);
        bt.root.left.left=new Node(8);
        bt.root.left.right=new Node(25);
        bt.root.right.left=new Node(42);
        bt.root.right.right=new Node(50);
        System.out.println("The preorder traversal of the binary tree is: ");
        bt.preorder(bt.root);
    }
}

The output of the program to traverse a binary tree using preorder traversal: