Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Breadth-first traversal
7.
Tree Traversal technique to get Sorted Node 
8.
Frequently Asked Questions
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)
binary tree

 

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.

Types of Binary Trees


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.

Complete 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).

Perfect Binary Tree


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.

Balanced Binary Tree

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

Degenerate Tree

 

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)
     
  2. Breadth-First order Traversal

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).

Tree

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).

Tree


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.
 

Binary Tree

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

Breadth-first traversal

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;
import java.util.LinkedList;
public class Solution {


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

}

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.

Tree Traversal Techniques


Output we receive: 1,2,3,4,5,6,7

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

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 -

 

Recommended Reading:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Modify a Binary Tree to get Preorder Traversal using Right Pointers only
Next article
How to Print a Binary Tree in Vertical Order | Part-1
Live masterclass