1.
What is a Binary Tree?
2.
What are the Types of Binary Trees?
3.
Different Types of Traversal in Binary Tree
4.
Depth First Traversal
5.
Advantages of Postorder traversal in Binary Tree
6.
7.
Tree Traversal technique to get Sorted Node
8.
8.1.
What are the different types of Binary Trees?
8.2.
What are Binary Trees?
8.3.
What are some of the advantages of using binary trees?
8.4.
What are some advantages of using post-order traversal in a binary tree?
8.5.
Which tree traversal can be used to get a sorted set of nodes from a binary tree?
9.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Traversal in Binary Tree

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## What is a Binary Tree?

A Binary Tree is a variety of Trees that has a maximum of two children. It has three parts mainly Associated with it i.e

1. Root Node
2. Left Node(Left Child)
3. Right Node(Right Child)

## What are the Types of Binary Trees?

1-Full Binary Tree: It is a variety of Binary Tree With either zero or two Nodes as Children.

2-Complete Binary TreeIt is a type of Binary Tree in which all Levels of a Binary Tree are Filled except the last Level of the Binary Tree.

3-Perfect Binary Tree: It is a type of Binary Tree in which all levels are filled. A unique point about a perfect Binary Tree is no leaf node (node at last level is internal node plus one).

4-Balanced Binary tree(AVL tree): It is a type of Binary Tree in which the difference b/w left and right subTree is a max of one. It is also known as the AVL tree.

5-Degenerate Tree: It is a Binary Tree Where every Node has either Zero or one parent.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Different Types of Traversal in Binary Tree

Traversal in Binary Tree is Mainly done in three ways, and that is:

1. Depth First-Order Traversal
Pre-Order (Left, Root, Right)
In-Order (Root, Left, Right)
Post-Order (Left, Right, Root)

## Depth First Traversal

1: In order Traversal
This is a variety of Depth tree traversal in which First, we traverse the left part of the tree using Recursion, then cross the root node, and then we travel the right amount of the tree.

Algorithm
A:-Traverse the left subtree.(i.e call Inorder(root->left).
B:-Visit The RootNode.
C:-Traverse the Right half of the Binary Tree(i.e. call      Inorder(root->right).

Output:4,2,5,1,6,3,7;

Benefits of Inorder Traversal
The main benefit of inorder traversal is it gives nodes in non -Decreasing order .it can also be used to get the nodes of Binary Sorted Tree using its variation

2: Pre-Order Traversal
This is a variety of Depth Binary Tree Traversal in Which First we Visit the Root then we visit the right half of the Tree, and then we visit the left half of the Binary tree.

Algorithm
A:-Visit the  Root Node.
B:-Traverse the left subtree.(i.e call Pre-order(root->left).
C:-Traverse the Right half of the Binary Tree(i.e. call      Pre-Order(root->right).

Output: 1,2,4,5,3,6,7;

Benefits of Pre-OrderTraversal
For Creating a Copy Of the Tree Preorder Traversal is used.
It is also used to get Prefix -expression Of an Expression Tree. the

3: Post-Order Traversal
It is a variety of Depth Binary Traversal in which First we Traverse the Left Subtree, and then we traverse Right Subtree, then We Traverse the Root Node.

Algorithm:
A:-Traverse the left subtree.(i.e call Post-order(root->left).
B:-Traverse the Right half of the Binary Tree(i.e. call  POst-Order(root->right).
C:-Visit the Root Node.

Output:4,5,2,1,6,3,7;

Before proceeding, let's watch the below video to see how Preorder, Inorder, and Postorder traversals are implemented in both recursive and iterative fashion.

## Advantages of Postorder traversal in Binary Tree

It is used to delete a given Binary Tree. It is also the used to get Postfix Expression of an Expression Tree.

Code in java:

//Binary Tree Node
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
//Main Class
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
/*  postorder traversal. */
void printPostorder(Node node)
{
//Base case
if (node == null)
return;
//left traversal
printPostorder(node.left);
//right traversal
printPostorder(node.right);
//visit root node
System.out.print(node.key + " ");
}

/*inorder*/
void printInorder(Node node)
{
//Base case
if (node == null){
return;
}
//left sub Tree
printInorder(node.left);
//Root node
System.out.print(node.key + " ");
//Right node
printInorder(node.right);
}

/*  print Binary Tree in preorder*/
void printPreorder(Node node)
{
if (node == null){
return;
}
System.out.print(node.key + " ");
printPreorder(node.left);
printPreorder(node.right);
}

// Wrappers over above recursive functions
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }

// Driver method
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
//Pre-order Traversal in Binary Tree
tree.printPreorder();
//Inorder traversal in Binary Tree
tree.printInorder();
//PostOrder Traversal in Binary Tree
tree.printPostorder();
}
}

It is a variety of binary-tree traversal in which we first traverse all the nodes at the current level then we move to the next level of the binary tree.

Algorithm:
Create a queue in which add the root node, then add the null and start to print the element of the queue by removing that element and adding all its children in the queue, once null is encountered that means we have moved to the next level.

Code:

import java.util.Queue;
public class Solution {

public static void printLevelWise(BinaryTreeNode<Integer> root) {
while(!q1.isEmpty()){
BinaryTreeNode<Integer> front=q1.poll();
if(front!=null){
System.out.print(front.data+":");
if(front.left!=null){
System.out.print("L:"+front.left.data+",");
}else{
System.out.print("L:"+"-1"+",");
}
if(front.right!=null){
System.out.print("R:"+front.right.data);
}else{
System.out.print("R:"+"-1");
}
System.out.println();

}
}

}

}

## Tree Traversal technique to get Sorted Node

In the Case of the Sorted Binary tree (i.e. Binary Search Tree), we use the Inorder Tree traversal Technique to get Sorted Output.

Check out this problem - Mirror A Binary Tree

### What are the different types of Binary Trees?

There are five types of binary trees:
Full Binary tree
Complete Binary tree
Balanced Binary Tree
Perfect Binary Tree
Degenerate Binary Tree

### What are Binary Trees?

Tree with a maximum of two child nodes.

### What are some of the advantages of using binary trees?

Comparison of two data can be achieved with ease.

### What are some advantages of using post-order traversal in a binary tree?

It is used to get Reverse Polish Notations.

### Which tree traversal can be used to get a sorted set of nodes from a binary tree?

In order, traversal can be used to get sorted nodes.

## Conclusion

The blog explained various types of Binary trees and the various types of depth First Traversal.

Recommended problems -