The easiest way to implement the preOrder traversal of a binary tree in Java is by using

On breadth-first traversal, you visit the tree on its breadth i.e. all nodes of one level is visited before you start with another level top to bottom. The PreOrder, InOrder, and PostOrder

While traversing a tree, you need to visit three elements, root node, left subtree, and right subtree. The order in which you visit these three nodes, determine the type of algorithms.

In PreOrder, you visit the root or node first, followed by left subtree and the right subtree, but in post order algorithm, you visit the root node at the last.

Now you should get the point that why this algorithm is called pre-order? well, because the order is determined by root, if you visit the root first, its preOrder, if you visit the root second its inOrder and if you visit the root third, or last, its post-order traversal.

Apart from these three basic traversal algorithms, there are also more sophisticated algorithms to traverse a binary tree, you can check a comprehensive course like

##

As I told you before, the based algorithms are naturally recursive because a binary tree is a recursive data structure. In order to visit the binary tree in preorder you can follow the following steps:

Though, you should not use recursion in production because it's prone to StackOverFlowError if a binary tree is too big to fit in memory. You should use an iterative algorithm in production to solve problems as seen earlier in Fibonacci and Palindrome problems.

You can also refer a good course on data structure and algorithm to learn various ways to convert a recursive algorithm to iterative one like one way to convert a recursive algorithm to iterative one is by using an explicit Stack,

is a nice course to learn algorithms and Fundamental data structure.

Btw, you would need a Pluralsight membership to access this course which cost around $29 per month or $299 per year. I have that and I advise all programmer to join Pluralsight because it's very important to upgrade your skills.

Even if you don't have a membership, don't worry, you can still access this course by taking their

##

Here is our sample program to visit all nodes of a binary tree in preorder. In this program, we have a class called BinaryTree, which represent a binary tree. It consists of a TreeNode called root, which is the starting point of traversal in a binary tree. The root then refers to other tree nodes via left and right links.

The logic of pre-order traversal is coded on preOrder(TreeNode node) method. The recursive algorithm first visits the node e.g. it prints it the value then recursive call the preOrder() method with left subtree, followed by right subtree.

I have another method preOrder() just to encapsulate the logic and make it easier for clients to call this method

Here is also a nice diagram which also shows how the pre-order algorithm traverses a binary tree. . If you like books, you can also see Introduction to Algorithms by Thomas H. Corman to learn more about binary tree algorithms.

###

Finally here is our Java program to traverse a binary tree in pre-order. The nodes are printed accordingly.

You can see that nodes are printed as per the pre-order traversal algorithm. The root node is always get printed first in pre-order traversal and in last on post-order traversal algorithm.

That's all about

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Introduction to Algorithms by Thomas H. Corman

Free Data Structure and Algorithm Courses

*recursion*. The recursive solution is hardly 3 to 4 lines of code and exactly mimic the steps, but before that, let's revise some basics about a binary tree and preorder traversal. Unlike array and linked list which have just one way to traverse, I mean linearly, binary tree has several ways to traverse all nodes because of its hierarchical nature like level order, preorder, postorder and in order. Tree traversal algorithms are mainly divided into two categories, the depth-first algorithms, and breadth-first algorithms. In depth-first, you go deeper into a tree before visiting the sibling node, for example, you go deep following the left node before you come back and traverse the right node.On breadth-first traversal, you visit the tree on its breadth i.e. all nodes of one level is visited before you start with another level top to bottom. The PreOrder, InOrder, and PostOrder

**traversals are all examples of depth-first traversal algorithms.**While traversing a tree, you need to visit three elements, root node, left subtree, and right subtree. The order in which you visit these three nodes, determine the type of algorithms.

In PreOrder, you visit the root or node first, followed by left subtree and the right subtree, but in post order algorithm, you visit the root node at the last.

Now you should get the point that why this algorithm is called pre-order? well, because the order is determined by root, if you visit the root first, its preOrder, if you visit the root second its inOrder and if you visit the root third, or last, its post-order traversal.

Apart from these three basic traversal algorithms, there are also more sophisticated algorithms to traverse a binary tree, you can check a comprehensive course like

**Data Structures and Algorithms: Deep Dive Using Java**to learn more about different types of tree e.g. self-balanced trees and other tree algorithms like level order traversal.##
__Binary Tree PreOrder traversal in Java using Recursion__

As I told you before, the based algorithms are naturally recursive because a binary tree is a recursive data structure. In order to visit the binary tree in preorder you can follow the following steps:- visit the node or root
- visit the left tree
- visit the right tree

private void preOrder(TreeNode node) { if (node == null) { return; } System.out.printf("%s ", node.data); preOrder(node.left); preOrder(node.right); }You can see the code is exactly written as the steps shown above, except the base case which is very important in a recursive algorithm you can read the code like steps. This is the power of recursion, it makes code concise and highly readable.

Though, you should not use recursion in production because it's prone to StackOverFlowError if a binary tree is too big to fit in memory. You should use an iterative algorithm in production to solve problems as seen earlier in Fibonacci and Palindrome problems.

You can also refer a good course on data structure and algorithm to learn various ways to convert a recursive algorithm to iterative one like one way to convert a recursive algorithm to iterative one is by using an explicit Stack,

**Algorithms and Data Structures - Part 1 and 2**courses on Pluralsight.is a nice course to learn algorithms and Fundamental data structure.

Btw, you would need a Pluralsight membership to access this course which cost around $29 per month or $299 per year. I have that and I advise all programmer to join Pluralsight because it's very important to upgrade your skills.

Even if you don't have a membership, don't worry, you can still access this course by taking their

**10-day free pass**which provides 200 minutes of free access to all of their 5000+ courses.##
__Java Program to implement PreOrder traversal of Binary Tree__

Here is our sample program to visit all nodes of a binary tree in preorder. In this program, we have a class called BinaryTree, which represent a binary tree. It consists of a TreeNode called root, which is the starting point of traversal in a binary tree. The root then refers to other tree nodes via left and right links.The logic of pre-order traversal is coded on preOrder(TreeNode node) method. The recursive algorithm first visits the node e.g. it prints it the value then recursive call the preOrder() method with left subtree, followed by right subtree.

I have another method preOrder() just to encapsulate the logic and make it easier for clients to call this method

Here is also a nice diagram which also shows how the pre-order algorithm traverses a binary tree. . If you like books, you can also see Introduction to Algorithms by Thomas H. Corman to learn more about binary tree algorithms.

###
__PreOrder traversal in Java__

Finally here is our Java program to traverse a binary tree in pre-order. The nodes are printed accordingly.__PreOrder traversal in Java__

/* * Java Program to traverse a binary tree using PreOrder traversal. * In PreOrder the node value is printed first, followed by visit * to left and right subtree. * input: * A * / \ * B E * / \ \ * C D F * * output: A B C D E F */ public class Main { public static void main(String[] args) throws Exception { // construct the binary tree given in question BinaryTree bt = new BinaryTree(); BinaryTree.TreeNode root = 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 in preOrder traversal System.out.println("printing nodes of a binary tree in 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; } } // root of binary tree TreeNode root; /** * Java method to print tree nodes in PreOrder traversal */ public void preOrder() { preOrder(root); } /** * traverse the binary tree in PreOrder * @param node - starting node, root */ 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 A B C D E F

You can see that nodes are printed as per the pre-order traversal algorithm. The root node is always get printed first in pre-order traversal and in last on post-order traversal algorithm.

That's all about

**how to traverse a binary tree in PreOrder traversal in Java**. The recursive algorithm is very simple and hardly required 3 to 4 lines of code. Just remember that in preOrder traversal you visit node first, followed by left subtree and finally right subtree.**Further Learning**

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Introduction to Algorithms by Thomas H. Corman

Free Data Structure and Algorithm Courses

**Other Binary Tree Tutorials and Interview Questions**

If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :

- 50+ Data Structure and Algorithms Problems from Interviews (list)
- 5 Books to Learn Data Structure and Algorithms in depth (books)
- How to print all leaf nodes of a binary tree in Java? (solution)
- How to implement a binary search tree in Java? (solution)
- How to implement a recursive preorder algorithm in Java? (solution)
- Recursive Post Order traversal Algorithm (solution)
- How to print leaf nodes of a binary tree without recursion? (solution)
- 75+ Coding Interview Questions for Programmers (questions)
- Iterative PreOrder traversal in a binary tree (solution)
- How to count the number of leaf nodes in a given binary tree in Java? (solution)
- 100+ Data Structure Coding Problems from Interviews (questions)
- Recursive InOrder traversal Algorithm (solution)
- Post order binary tree traversal without recursion (solution)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)

Thanks for reading this coding interview question so far. If you like this String interview question then please share with your friends and colleagues. If you have any question or feedback then please drop a comment.

**P. S.**- If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the**Easy to Advanced Data Structures**course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.
## No comments:

## Post a Comment