This post talks about PreOrder traversal of binary tree implementation in Java
This is the simplest traversal. In this traversal each node is processed before the subtrees, it still requires that some information must be maintained while moving down the tree. in the below picture, 1 then the left subtree, and this is followed by the right subtree.
PreOrder traversal is defined as follows:
- Visit the root
- Traverse the Left Subtree
- Traverse the Right Subtree
PreOrder, traversal can be implemented either recursive and iterative approach. Both Approaches have shown below:
Recursive Approach:
|
1 2 3 4 5 6 7 8 9 10 11 |
/** * Recursive method for Binary Tree preOrder Processing * @param root Node */ public void preOrderRecursive(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrderRecursive(root.left); preOrderRecursive(root.right); } } |
Time Complexity: O(n) and Space Complexity: O(n)
Iterative Approach:
In the Iterative approach, A stack is required as we need to remember the current node so that after completing the left subtree. we can go to the right subtree. We have to simulate the same, first, we process the current node and before going to the left subtree. we store the current node on the stack. After completing the left subtree processing, pop the element and go to the right subtree. We have to continue this process until the stack is non-empty.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Iterative method for Binary Tree preOrder Processing * @param root Node */ public ArrayList<Node<E>> preOrderIterative(Node<E> root) { ArrayList<Node<E>> preOrderList = new ArrayList<>(); if(root == null) { return preOrderList; } Stack<Node<E>> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { Node<E> temp = stack.pop(); preOrderList.add(temp); if(temp.right != null) { stack.push(temp.right); } if(temp.left != null) { stack.push(temp.left); } } return preOrderList; } |
Time Complexity: O(n) and Space Complexity: O(n)
Below is the Complete Source code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
package com.kkjavatutorials.tree; import java.util.ArrayList; import java.util.Stack; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for Binary Tree preOrder Processing * @param root Node */ public void preOrderRecursive(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrderRecursive(root.left); preOrderRecursive(root.right); } } /** * Iterative method for Binary Tree preOrder Processing * @param root Node */ public ArrayList<Node<E>> preOrderIterative(Node<E> root) { ArrayList<Node<E>> preOrderList = new ArrayList<>(); if(root == null) { return preOrderList; } Stack<Node<E>> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { Node<E> temp = stack.pop(); preOrderList.add(temp); if(temp.right != null) { stack.push(temp.right); } if(temp.left != null) { stack.push(temp.left); } } return preOrderList; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
package com.kkjavatutorials.client; import java.util.ArrayList; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to test preOrder Processing of Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); //Root Node Node<Integer> rootNode = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right of root Node rootNode.left = secondNode; rootNode.right = thirdNode; rootNode.left.left = fourthNode; rootNode.left.right = fifthNode; rootNode.right.left = sixthNode; rootNode.right.right = seventhNode; //Call for preOrder processing System.out.println(".....Binary Tree PreOrder Processing output using Recursive method...."); binaryTree.preOrderRecursive(rootNode); System.out.println(); System.out.println(".....Binary Tree PreOrder Processing output using Iterative method...."); ArrayList<Node<Integer>> preOrderIterative = binaryTree.preOrderIterative(rootNode); for (Node<Integer> node : preOrderIterative) { System.out.print(node.data+" "); } } } |
The output of This Program:
…..Binary Tree PreOrder Processing output using Recursive method….
1 2 4 5 3 6 7
…..Binary Tree PreOrder Processing output using Iterative method….
1 2 4 5 3 6 7
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Binary Tree Traversals
That’s all about PreOrder traversal of binary tree implementation in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.