C++ Program for Diagonal Traversal of Binary Tree
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++
Leave a Reply