Table of Contents
If you want to practice data structure and algorithm programs, you can go through top 100+ data structure and algorithm interview questions.
1. Introduction
In this article, we will explore the concept of InOrder traversal in binary trees, focusing on its implementation in Java. In computer science, a binary tree is a foundational data structure, and traversing it is a fundamental technique. Among the various traversal methods, PreOrder traversal is widely used due to its applications across a range of algorithms and operations.
2. What is PreOrder Traversal?
3. Process of PreOrder Traversal
Visitthe node.- Traverse the
left subtreein PreOrder. - Traverse the
right subtreein PreOrder.
4. Implementation
There can be two ways of implementing it:
- Recursive
- Iterative
4.1 Recursive Solution
Recursive solution is very straight forward. Below diagram will make you understand recursion better.
Code for recursion will be:
|
1 2 3 4 5 6 7 8 9 10 |
public void preorder(TreeNode root) { if(root != null) { //Visit the node by Printing the node data System.out.printf("%d ",root.data); preorder(root.left); preorder(root.right); } } |
The time complexity for recursive approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.
The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of the call stack to handle recursion. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).
4.2 Iterative Solution
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
- Create empty
stackand pust root node to it. - Do the following when
stackis not empty- Pop a node from
stackand print it - Push
right childof popped node tostack - Push
left childof popped node to stack
- Pop a node from
We are pushing right child first, so it will be processed after left subtree as Stack is LIFO.
|
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 |
public void preorderIter(TreeNode root) { if(root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.empty()){ TreeNode n = stack.pop(); System.out.printf("%d ",n.data); if(n.right != null){ stack.push(n.right); } if(n.left != null){ stack.push(n.left); } } } |
The time complexity for iterative approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.
The space complexity is O(h), where h is the height of the tree. This complexity arises from the use of an explicit stack to keep track of nodes. In the worst case (a skewed tree), the height of the tree can become n, making the space complexity O(n).
5. Complete Java Program
Let’s say our binary tree is:
Here is complete java program for PreOrder traversal:
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
import java.util.Stack; public class BinaryTreePreOrder { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } } // Recursive Solution public void preorder(TreeNode root) { if(root != null) { //Visit the node-Printing the node data System.out.printf("%d ",root.data); preorder(root.left); preorder(root.right); } } // Iterative solution public void preorderIter(TreeNode root) { if(root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.empty()){ TreeNode n = stack.pop(); System.out.printf("%d ",n.data); if(n.right != null){ stack.push(n.right); } if(n.left != null){ stack.push(n.left); } } } public static void main(String[] args) { BinaryTreePreOrder bi=new BinaryTreePreOrder(); // Creating a binary tree TreeNode rootNode=createBinaryTree(); System.out.println("Using Recursive solution:"); bi.preorder(rootNode); System.out.println(); System.out.println("-------------------------"); System.out.println("Using Iterative solution:"); bi.preorderIter(rootNode); } public static TreeNode createBinaryTree() { TreeNode rootNode =new TreeNode(40); TreeNode node20=new TreeNode(20); TreeNode node10=new TreeNode(10); TreeNode node30=new TreeNode(30); TreeNode node60=new TreeNode(60); TreeNode node50=new TreeNode(50); TreeNode node70=new TreeNode(70); rootNode.left=node20; rootNode.right=node60; node20.left=node10; node20.right=node30; node60.left=node50; node60.right=node70; return rootNode; } } |
Run above program and you will get following output:
40 20 10 30 60 50 70
————————-
Using Iterative solution:
40 20 10 30 60 50 70
6. Conclusion
In this article, we covered about Binary tree PreOrder traversal and its implementation. We have done traversal using two approaches: Iterative and Recursive. We also discussed about time and space complexity for the PreOrder traversal.
Java Binary tree tutorial:
- Binary tree in java
- Binary tree preorder traversal
- Binary tree postorder traversal
- Binary tree inorder traversal
- Binary tree level order traversal
- Binary tree spiral order traversal
- Binary tree reverse level order traversal
- Binary tree boundary traversal
- Print leaf nodes of binary tree
- Count leaf nodes in binary tree
- get maximum element in binary tree
- Print all paths from root to leaf in binary tree
- Print vertical sum of binary tree in java
- Get level of node in binary tree in java
- Lowest common ancestor(LCA) in binary tree in java
