Tuesday, May 3, 2022

Question 56 : How can you traverse binary tree?

There are three ways to traverse a binary tree

PreOrder traversal:

In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.
Steps for PreOrder traversal are:
• `Visit` the node.
• Traverse the `left subtree` in PreOrder.
• Traverse the `right subtree` in PreOrder.

There can be two ways of implementing it.

• Recursive
• Iterative

Recursive solution:
Recursive solution is very straight forward.Below diagram will make you understand recursion better.

Code for recursion will be::

``````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);
}
}``````

Iterative solution:
For recursion, we use the implicit stack. So here to convert the recursive solution to iterative, we will use the explicit stack.
Steps for iterative solution:

1. Create empty `stack` and pust root node to it.
2. Do the following when `stack` is not empty
• Pop a node from `stack` and print it
• Push `right child` of a popped node to `stack`
• Push `left child` of a popped node to stack

We are pushing the right child first, so it will be processed after the left subtree as Stack is LIFO.:

``````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);
}

}

}``````

Example:
Let's say your binary tree is

Let's create a java program for PreOrder traversal::

``````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 the above program and you will get the following output::
``````Using Recursive solution:
40 20 10 30 60 50 70
————————-
Using Iterative solution:
40 20 10 30 60 50 70``````

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS