Home Â» Technical Interview Questions Â» Tree Interview Questions Â» Diagonal Traversal of Binary Tree

# Diagonal Traversal of Binary Tree

## Problem Statement

The problem “Diagonal Traversal of Binary Tree” states that you are given a binary tree and now you need to find the diagonal view for the given tree. When we see a tree from the top-right direction. The nodes which are visible to us is the diagonal view of the binary tree.

## Example

2 7
3 4
5 6

Explanation

The first diagonal has nodes 2, 7 in there. Then the second diagonal has 3, 4, similarly for the third diagonal 5, 6. Thus the output has printed in a way such that the elements from the same diagonal have in the same line.

## Approach

The problem asks us to print the nodes which are visible to us from the top-right direction. So how do we solve the problem?

We will do an inorder traversal of the binary tree. While doing this, we will keep track of the distance in a diagonal direction. Whenever we move in the left direction we add 1 to the diagonal distance and if we moved in the right direction we don’t add any value to the distance. So, while doing this we will keep track of the nodes visited in a map. We will create a map with diagonal distance as key and a vector as value. because we will add the nodes with diagonal distance in a vector. And as we would have traversed through the whole tree. After the traversal, we would have kept the nodes in the vectors as per their diagonal distance.

After all of these calculations, simply print the elements in the map while separating the nodes from each of the vectors.

## C++ code to print Diagonal Traversal of Binary Tree

#include <bits/stdc++.h>
using namespace std;

struct node{
int data;
node *left, *right;
};

node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
return tmp;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
if(root){
m[dis].push_back(root->data);
// move in the left direction with dis+1 distance
diagonalView(root->left, dis+1, m);
// move in the right direction with dis distance
diagonalView(root->right, dis, m);
}
}

int main(){
node *root = create(2);
root->left = create(3);
root->right = create(7);
root->left->left = create(5);
root->left->right = create(4);
root->left->right->left = create(6);

map<int, vector<int>> m;
diagonalView(root, 0, m);
for(auto x: m){
for(auto nodes: x.second)
cout<<nodes<<" ";
cout<<endl;
}
}
2 7
3 4
5 6

## Java code to print Diagonal Traversal of Binary Tree

import java.util.*;

class node{
int data;
node left, right;
}

class Main{

static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = tmp.right = null;
return tmp;
}

static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
if(root != null){
Vector<Integer> v = m.get(dis);
if(v == null){
v = new Vector<Integer>();
}
else
m.put(dis, v);
// move in the left direction with dis+1 distance
diagonalView(root.left, dis+1, m);
// move in the right direction with dis distance
diagonalView(root.right, dis, m);
}
}

public static void main(String[] args){
node root = create(2);
root.left = create(3);
root.right = create(7);
root.left.left = create(5);
root.left.right = create(4);
root.left.right.left = create(6);

Map<Integer, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
diagonalView(root, 0, m);
for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
System.out.println(entry.getValue());
}
}
[2, 7]
[3, 4]
[5, 6]

## Complexity Analysis

### Time Complexity

O(NlogN), because we have traversed the tree and have updated the values. Because we have used a map, insertion, deletion, and searching is done in O(logN) time.

READ  Convert a BST to a Binary Tree such that sum of all greater keys is added to every key

### Space Complexity

O(N), because we are storing all the nodes in the map. The space complexity is linear.

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions