Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 1 - Iterative Approach
2.1.
Implementation
2.2.
Time and Space Complexity
3.
Approach 2 - Recursive Approach
3.1.
Implementation
3.2.
Time and Space Complexity
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is the Diagonal traversal of a Binary Tree?
4.3.
What is the best-case time complexity for the Diagonal traversal of a Binary Tree?
4.4.
What are the different possible Traversals for Binary Trees?
5.
Conclusion
Last Updated: Mar 27, 2024

Diagonal Traversal of Binary Tree (Recursive and Iterative)

Author Raksha Jain
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Today, let's learn about a famous and commonly asked Interview Problem, i.e., the Diagonal Traversal of a Binary Tree.
So, Binary Tree is a generic tree with only two children, i.e., left and right. And Diagonal Traversal of a Binary Tree here means that we need to traverse diagonally by diagonal and print all the nodes occurring in a diagonal.   

Problem Statement: Given the root of the binary tree, we need to return the diagonal traversal(lines of slope -1) of its nodes' values.

Example: 

illustration image

Let's divide the entire Binary Tree into diagonals(slopes of lines -1). Now, traversing along diagonals, we print all the nodes we encounter. 

So, 
Nodes that lie along the Diagonal
On Diagonal 1 - 8 10 14
On Diagonal 2 - 3 6 7 13
On Diagonal 3 - 1 4 
So, the Diagonal Traversal of the given Binary Tree would be: 8 10 14 3 6 7 13 1 4

There is both a recursive and an iterative approach to printing the Diagonal Traversal of a Given Binary Tree. Let's discuss both of them in detail. 

Recommended: Try the Problem yourself before moving on to the solution. 

Approach 1 - Iterative Approach

Here, we start by printing our current node and adding a NULL in our queue. We use a queue data structure to store the current node's left child and move our pointer to the right child of the node.

We continue this process till the right child exists. Once the process ends, we look for the nodes in the queue. If the queue stores a NOT NULL node, we continue the same process. However, if it's a NULL node, it acts as a delimiter, guiding us that the incoming nodes now are of new diagonal and hence have to be printed in a new line. We pop this NULL node and add another NULL node in the queue at the same time if the size of the queue is non-zero after popping the NULL node indicating the presence of the next diagonal.

Let us look at an example to get a more clear picture of the above algorithm.

Example : 

illustration image

Initially Output displays [3] i.e. the root’s data and queue stores [NULL] node.

Now, the process starts for the root node.
Its left child is entered in the queue and the pointer to the current node points to the right child.

Print/Output Screen Queue

Step1:  3 [NULL, 9]   ---> Pointer now moves to 20

Step2:  3 20 [NULL, 9,15]   ---> Pointer now moves to 7

Step3:  3 20 7 [NULL, 9,15]   ---> Pointer now moves to NULL

Since, the current node is NULL now, the inner while loop breaks, and NULL (first element of queue is popped out). 
Since, the popped element = NULL, a new line is printed hence starting with a new diagonal. Also, NULL is entered in the queue.

Step4:  3 20 7 [9,15,NULL]  

Step5:  3 20 7
             9 [15, NULL]   ---> Pointer now moves to 9

Step6:  3 20 7
             9 15 [NULL]   ---> Pointer now moves to 15

Implementation

Let’s have a look at its implementation in Java 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    public static void diagonalTraversal(TreeNode root) {
        // edge case
        if (root == null)
            return;
       
        // using queue of Treenode
        Queue<TreeNode> q = new LinkedList<>();
       
        // adding root and NULL delimiter in queue
        q.add(root);
        q.add(null);
       
        while (q.size()>0) {
            TreeNode temp = q.peek();
            q.remove();
       
            // if current node is NULL, 
            //insert another NULL for next diagonal
            if (temp == null) {
       
                // if queue is empty return
                if (q.size()==0)
                    return;
       
                System.out.println();
                // Adding another delimiter
                q.add(null);
            }
            else {
                while (temp!=null) {
                    System.out.print( temp.val + " ");
       
                    // add left child of current node in queue 
                    if (temp.left!=null)
                        q.add(temp.left);
       
                    // Moving temp to right child of current node
                    temp = temp.right;
                }
            }
        }
    }
    
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("Form a tree: ");
        TreeNode root = new TreeNode(s.nextInt());
        root.left = new TreeNode(s.nextInt());
        root.right = new TreeNode(s.nextInt());
        root.right.left = new TreeNode(s.nextInt());
        root.right.right = new TreeNode(s.nextInt());

        System.out.println("Diagonal Traversal of Binary Tree ");
        diagonalTraversal(root);
    }
}


Output:

Form a tree: 3 9 20 15 7 
Diagonal Traversal of Binary Tree 

3 20 7 

9 15 

Time and Space Complexity

Time Complexity: O(n) as we are traversing all the nodes of the Binary tree in Diagonal traversal of the Binary Tree at least once.

Space Complexity: O(n) as extra space for storing the left child of the current nodes in a queue, where n is the number of nodes in the Binary Tree.

Read More - Time Complexity of Sorting Algorithms

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

Approach 2 - Recursive Approach

In the recursive approach, we keep an ordered map (i.e., TreeMap in Java) to store different diagonals and nodes corresponding to that diagonal. 
Hence, helping us to print the nodes order-wise.  

Here, a diagonal Traversal function is called which creates a TreeMap named “diagonal” which stores the set of values corresponding to given diagonal d in a vector k . This calls the Recursive function with 0 as the initial d (diagonal value). 

The Recursive function then creates a vector corresponding to the d’s value, if the vector corresponding to d is null, else the node is stored in the existing vector k corresponding to the diagonal valued.

In the end, two recursive calls are made: 
One for left child: diagonalRecursive(root.left, d + 1, diagonal)
Other for the right child :  diagonalRecursive(root.right, d, diagonal)

Implementation

Let’s have a look at its implementation in Java 

import java.util.*;
import java.util.TreeMap;
import java.util.Vector;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    static void diagonalRecursive(TreeNode root,int d, TreeMap<Integer,Vector<Integer>> diagonal) {
         
         // Base case
        if (root == null)
            return;
         
        // get the list at the particular diagonal
        Vector<Integer> k = diagonal.get(d);
         
        // current diagonal is null then 
        //create a vector and store the data
        if (k == null){
            k = new Vector<>();
            k.add(root.val);
        }
         
        // current diagonal is not null then update the list
        else{
            k.add(root.val);
        }
         
        // Store all nodes of same diagonal together
        diagonal.put(d,k);
         
        // Increase the vertical distance if left child exists
        diagonalRecursive(root.left, d + 1, diagonal);
          
        // Vertical distance remains if same for right child
        diagonalRecursive(root.right, d, diagonal);
    }
     
    
    public static void diagonalTraversal(TreeNode root) {
         
        // creating a map of vectors to store Diagonal elements
        TreeMap<Integer,Vector<Integer>> diagonal = new TreeMap<>();
        diagonalRecursive(root, 0, diagonal);
         
        for (int key : diagonal.keySet()){
            System.out.println(diagonal.get(key));
        }
    }
    
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("Form a tree: ");
        TreeNode root = new TreeNode(s.nextInt());
        root.left = new TreeNode(s.nextInt());
        root.right = new TreeNode(s.nextInt());
        root.right.left = new TreeNode(s.nextInt());
        root.right.right = new TreeNode(s.nextInt());
        
        System.out.println("Diagonal Traversal of Binary Tree ");
        diagonalTraversal(root);
    }
}


Output:

Form a tree: 3 9 20 15 7 
Diagonal Traversal of Binary Tree 

[3, 20, 7]

[9, 15]

Time and Space Complexity

Time Complexity: O(nlogn). O(n) as we are traversing all the nodes of the Binary tree in Diagonal traversal of Binary Tree at least once and O(logn) for adding elements in a Tree Map data structure.

Space Complexity: O(n) as extra space for storing all the nodes of the Binary tree in the Treemap data structure.
Where n is the number of nodes in the Binary Tree.

Frequently Asked Questions

What is a Binary Tree?

A generic tree with at most two child nodes for each parent node is known as a Binary Tree. An empty tree is also considered a valid Binary Tree.

What is the Diagonal traversal of a Binary Tree?

Diagonal Traversal of a Binary Tree here means that we need to traverse diagonally by diagonal and print all the nodes occurring in a diagonal.    

What is the best-case time complexity for the Diagonal traversal of a Binary Tree?

The best-case time complexity for Diagonal Traversal of a Binary Tree is O(1), i.e. when only a single or no node is present in the Binary Tree.

What are the different possible Traversals for Binary Trees?

The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal, etc.

Conclusion

In this blog, we learned various approaches for the Diagonal traversal of Binary Trees.

  • Diagonal Traversal of a Binary Tree here means that we need to traverse diagonally by diagonal and print all the nodes occurring in a diagonal.    
  • The minimum space complexity required is O(n) where n = number of nodes in a Binary Tree as we need to store all the nodes of a Binary Tree in any used data structure.
  • The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal, etc.
     

Check out more blogs on different traversals of Binary Tree like Diagonal Traversal, and Level Order Traversal to read more about these topics in detail. And if you liked this blog, share it with your friends!

Recommended Reading:

Recommended problems -

 

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, 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
Double Order Traversal of a Binary Tree
Next article
Specific Level Order Traversal of Binary Tree
Live masterclass