How to implement PreOrder traversal of Binary Tree inwards Java - Example Tutorial

The easiest means to implement the preOrder traversal of a binary tree inward Java is past times using recursion. The recursive solution is hardly 3 to four lines of code together with precisely mimic the steps, but before that, let's revise around basics virtually a binary tree together with preorder traversal. Unlike array together with linked list which bring simply 1 means to traversed i.e. linearly, binary tree has several ways to traverse all nodes e.g. preorder, postorder together with inorder. But, tree traversal algorithms are mainly divided into 2 categories, the depth-first algorithms, together with breadth-first algorithms. In depth-first, y'all become deeper into a tree before visiting the sibling node, for example, y'all become deep next left node before y'all come upwards dorsum together with traverse the correct node. On breadth-first traversal, y'all see the tree on its breadth i.e. all nodes of 1 score is visited before y'all start alongside around other score exceed to bottom. The PreOrder, InOrder, together with PostOrder traversals are all examples of depth-first traversal algorithms.

While traversing a tree, y'all demand to see 3 elements, source node, left subtree, together with correct subtree. The lodge inward which y'all see these 3 nodes, create upwards one's hear the type of algorithms. In PreOrder, y'all see the source or node first, followed past times left subtree together with the correct subtree, but inward post lodge algorithm, y'all see the source node at the last.

Now y'all should acquire the signal that why this algorithm is called pre-order? well, because the lodge is determined past times root, if y'all see the source first, its preOrder, if y'all see the source minute its inOrder together with if y'all see the source third, or last, its post order. See apart from these at that topographic point are to a greater extent than sophisticated algorithms to traverse a binary tree, come across Introduction to Algorithms to larn to a greater extent than virtually unlike types of tree e.g. self-balanced trees together with other tree algorithms e.g. score lodge traversal.

Binary Tree PreOrder traversal inward Java using Recursion

As I told y'all before, the based algorithms are naturally recursive because a binary tree is a recursive information structure. In lodge to see the binary tree inward preorder y'all tin follow next steps:

visit the node or root
visit the left tree
visit the correct tree

In lodge to see the left together with correct subtree, y'all tin simply telephone band the same method alongside left together with correct node. This is where recursion comes into play every bit shown inward next code snippet:

private void preOrder(TreeNode node) {     if (node == null) {       return;     }     System.out.printf("%s ", node.data);     preOrder(node.left);     preOrder(node.right); }

You tin come across the code is precisely written every bit the steps shown above, except the base of operations instance which is rattling of import inward a recursive algorithm y'all tin read the code similar steps. This is the ability of recursion, it makes code concise together with highly readable. Though, y'all should non role recursion inward production because it's prone to StackOverFlowError if a binary tree is also big to correspond inward memory. You should role an iterative algorithm inward production to solve problems every bit seen before inward Fibonacci together with palindrome problems.

You tin also refer a skilful mass on information construction together with algorithm to larn diverse ways to convert a recursive algorithm to iterative 1 e.g. 1 means to convert a recursive algorithm to iterative 1 is past times using an explicit Stack, Introduction to Algorithm past times Thomas H. Cormen is a wonderful mass to larn algorithms.

The easiest means to implement the preOrder traversal of a binary tree inward Java is past times using How to implement PreOrder traversal of Binary Tree inward Java - Example Tutorial

Java Program to implement PreOrder traversal of Binary Tree

Here is our sample programme to see all nodes of a binary tree inward preorder. In this program, nosotros bring a cast called BinaryTree, which stand upwards for a binary tree. It consists a TreeNode called root, which is the starting signal of traversal inward a binary tree. The source together with then refers to other tree nodes via left together with correct links.

The logic of pre-order traversal is coded on preOrder(TreeNode node) method. The recursive algorithm starting fourth dimension visits the node e.g. it prints it the value together with then recursive telephone band the preOrder() method alongside left subtree, followed past times correct subtree. I bring around other method preOrder() simply to encapsulate the logic together with become far easier for clients to telephone band this method.

Here is a overnice diagram which also shows how pre-order algorithm traverse a binary tree:

PreOrder traversal inward Java

/*  * Java Program to traverse a binary tree using PreOrder traversal.   * In PreOrder the node value is printed first, followed past times see  * to left together with correct subtree.   * input:  *     Influenza A virus subtype H5N1  *    / \  *   B   due east  *  / \   \  * C   D   F  *   * output: Influenza A virus subtype H5N1 B C D due east F   */  public class Main {    public static void main(String[] args) throws Exception {      // laid upwards the binary tree given inward question     BinaryTree bt = new BinaryTree();     BinaryTree.TreeNode source = new BinaryTree.TreeNode("A");     bt.root = root;     bt.root.left = new BinaryTree.TreeNode("B");     bt.root.left.left = new BinaryTree.TreeNode("C");      bt.root.left.right = new BinaryTree.TreeNode("D");     bt.root.right = new BinaryTree.TreeNode("E");     bt.root.right.right = new BinaryTree.TreeNode("F");      // visitng nodes inward preOrder traversal     System.out.println("printing nodes of a binary tree inward preOrder using recursion");     bt.preOrder();    }  }  class BinaryTree {   static class TreeNode {     String data;     TreeNode left, right;      TreeNode(String value) {       this.data = value;       left = right = null;     }      boolean isLeaf() {       return left == null ? right == null : false;     }    }    // source of binary tree   TreeNode root;    /**    * Java method to impress tree nodes inward PreOrder traversal    */   public void preOrder() {     preOrder(root);   }    /**    * traverse the binary tree inward PreOrder    * @param node - starting node, source    */   private void preOrder(TreeNode node) {     if (node == null) {       return;     }     System.out.printf("%s ", node.data);     preOrder(node.left);     preOrder(node.right);   }  } Output printing nodes of a binary tree in preOrder using recursion Influenza A virus subtype H5N1 B C D due east F

You tin come across that nodes are printed every bit per the pre-order traversal algorithm. The source node is e'er acquire printed starting fourth dimension inward pre-order traversal together with inward lastly on post-order traversal algorithm.

That's all virtually how to traverse a binary tree inward PreOrder traversal inward Java. The recursive algorithm is rattling uncomplicated together with hardly required 3 to four lines of code. Just yell back that inward preOrder traversal y'all see node first, followed past times left subtree together with finally correct subtree.

Further Reading
Algorithms together with Data Structures - Part 1 together with 2
Java Fundamentals, Part 1 together with 2
Cracking the Coding Interview - 189 Questions together with Solutions

Other data construction together with algorithms tutorials for Java Programmers

How to contrary a linked listing inward Java without recursion? (solution)
How to implement binary search algorithm inward Java? (solution)
How to contrary an array inward house inward Java? (solution)
10 Algorithm books Every Programmer Should Read (list)
How to implement Insertion kind inward Java? (solution)
How to implement Quicksort algorithm inward Java? (solution)
How to discovery the length of singly linked listing inward Java? (solution)
How to discovery the missing publish inward an array of 1 to 100? (solution)
How to discovery all pairs on integer array whose amount is equal to given a number? (solution)
15 often asked information construction together with algorithm Interview Questions (list)
5 Books to larn information construction together with algorithms inward Java? (books)