C++ Program for Diagonal Traversal of Binary Tree

By Abhishiek Bhadauria

In this post, we are going to discuss the C++ program for the diagonal traversal of a binary tree. This code will help you to understand how the diagonal traversal of a binary tree happens. After that, I am going to explain what I have written in code.

C++ Code For Diagonal Traversal of Binary Tree

#include <bits/stdc++.h> 
using namespace std; 
struct Node 
{ 
    int data; 
    Node *left, *right; 
}; 
void diagonalprintUtil(Node* root, int d, 
                      map<int, vector<int>> &diagonalprint) 
{ 
    if (!root) 
        return; 
  
    diagonalprint[d].push_back(root->data); 
    diagonalprintUtil(root->left, d + 1, diagonalprint); 
    diagonalprintUtil(root->right, d, diagonalprint); 
} 
void diagonalprint(Node* root) 
{ 
    map<int, vector<int> > diagonalprint; 
    diagonalprintUtil(root, 0, diagonalprint); 
    cout<<"Diagonal Traversal of binary tree : n"; 
    for (auto it = diagonalprint.begin(); 
         it != diagonalprint.end(); ++it) 
    { 
        for (auto itr = it->second.begin(); 
             itr != it->second.end(); ++itr) 
            cout<<*itr<<' '; 
  
        cout<<'n'; 
    } 
} 
Node* newnode(int data) 
{ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
int main() 
{ 
    Node* root=newnode(80); 
    root->left=newnode(30); 
    root->right=newnode(100); 
    root->left->left=newnode(10); 
    root->left->right=newnode(60); 
    root->right->right=newnode(140); 
    root->right->right->left=newnode(130); 
    root->left->right->left=newnode(40); 
    root->left->right->right=newnode(70); 
    diagonalprint(root); 
    return 0; 
} 

Now let’s understand the working of code.

Firstly, we have imported all the C++ libraries by using bits/stdc++.h library. Then we defined a node using a structure.

Thereafter, we have defined a function named diagonalprintUtil which have 3 arguments:-root of a binary tree, d-distance of the current line from the rightmost top most slope, diagonalprint-a multimap to store diagonal elements.

Then we have stored all nodes of the same line as a vector and increased the vertical distance if the left child is there and vertical distance remains the same for the right child.

After that, we have created a new function name diagonalprint with only one argument:-node* root.

Here we printed the diagonal traversal of the tree. Therefore we created a utility function newnode to create a new node.

Finally, in main(), we have given the tree values and called diagonalprint() function.

Output:-

80 100 140
30 60 70 130
10 40

That’s it, Folks!

Thank You!

Also read: Closest leaf node to a given node in Binary Tree in C++