Finding Diagonal Traversal of The Binary Tree
Implementation
//Write down the main C++ program to check the implementation of the diagonal traversal of the binary tree.
#include <bits/stdc++.h>
using namespace std;
// creating a new tree node
struct __nod
{
int record;
__nod *Lft, *Rt;
};
/* Root- It is the root of the binary tree.
d – it is the distance from the current line of the right-most and top-most slope.
diagPrint – This will be used to store the elements of the diagonal, which is passed by reference.
*/
void diagPrintUtil(__nod* root, int d,
map<int, vector<int>> &diagPrint)
{
// writing the basic case.
if (!root)
return;
//Now, we will store all the nodes of the same line together, and that too in a vector.
diagPrint[d].push_back(root->record);
// We have to increment the vertical distance if the left child is: -
diagPrintUtil(root->Lft,
d + 1, diagPrint);
// the vertical distance from the right child will remain the same.
diagPrintUtil(root->Rt,
d, diagPrint);
}
// Now, start printing the diagonal traversal of the given binary tree.
void diagPrint(__nod* root)
{
// Now, we will start by creating the map of all the vectors and will be able to store all the elements provided by the diagonals.
map<int, vector<int> > diagPrint;
diagPrintUtil(root, 0, diagPrint);
cout << "Diagonal Traversal of binary tree: \n";
for (auto it:diagPrint)
{
vector<int> v=it.second;
for(auto it:v)
cout<<it<<" ";
cout<<endl;
}
}
// creating a new utility method that will create a new node
__nod* new__nod(int record)
{
__nod* __nod = new __nod;
__nod->record = record;
__nod->Lft = __nod->Rt = NILL;
return __nod;
}
// writing the main program to test the above functions.
int main()
{
__nod* root = new__nod(8);
root->Lft = new__nod(3);
root->Rt = new__nod(10);
root->Lft->Lft = new__nod(1);
root->Lft->Rt = new__nod(6);
root->Rt->Rt = new__nod(14);
root->Rt->Rt->Lft = new__nod(13);
root->Lft->Rt->Lft = new__nod(4);
root->Lft->Rt->Rt = new__nod(7);
/* __nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(9);
root->Lft->Rt = new__nod(6);
root->Rt->Lft = new__nod(4);
root->Rt->Rt = new__nod(5);
root->Rt->Lft->Rt = new__nod(7);
root->Rt->Lft->Lft = new__nod(12);
root->Lft->Rt->Lft = new__nod(11);
root->Lft->Lft->Rt = new__nod(10);*/
diagPrint(root);
return 0;
}
Output:
Example 2
# Writing the Python program to see the diagonal traversal of the binary tree.
# Creating a new tree node
class __nod:
# Building a constructor to create a new binary tree node.
def __init__(self, record):
self.record = record
self.Lft = None
self.Rt = None
/* Root- It is the root of the binary tree.
d – it is the distance from the current line of the right-most and top-most slope.
diagPrint – This will be used to store the elements of the diagonal, which is passed by reference.
*/
def diagPrintUtil(root, d, diagPrintMap):
# Writing the basic case.
If the root is None:
return
# Now, we will store all the nodes of the same line together, and that too in a vector.
try :
diagPrintMap[d].append(root.record)
except KeyError:
diagPrintMap[d] = [root.record]
# We have to increment the vertical distance if the left child is: -
diagPrintUtil(root.Lft,
d+1, diagPrintMap)
# The vertical distance from the right child will remain the same.
diagPrintUtil(root.Rt,
d, diagPrintMap)
# Now, start printing the diagonal traversal of the given binary tree.
def diagPrint(root):
# Create a space where we can store all the diagonal elements.
diagPrintMap = dict()
# finding out the diagonal traversal
diagPrintUtil(root, 0, diagPrintMap)
print ("Diagonal Traversal of binary tree: ")
for I in diagPrintMap:
for j in diagPrintMap[i]:
print (j,end=" ")
print()
# Driver Program
root = __nod(8)
root.Lft = __nod(3)
root.Rt = __nod(10)
root.Lft.Lft = __nod(1)
root.Lft.Rt = __nod(6)
root.Rt.Rt = __nod(14)
root.Rt.Rt.Lft = __nod(13)
root.Lft.Rt.Lft = __nod(4)
root.Lft.Rt.Rt = __nod(7)
diagPrint(root)
Output:
Example 3
//Write down the main Java program to check the implementation of the diagonal traversal of the binary tree.
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.Vector;
public class DiagonalTraversalBTree
{
// creating a new tree node
static class __nod
{
int record;
__nod Lft;
__nod Rt;
//creating a new constructor
__nod(int record)
{
this.record=record;
Lft = NILL;
Rt =NILL;
}
}
/* Root- It is the root of the binary tree.
d – it is the distance from the current line of the right-most and top-most slope.
diagPrint – This will be used to store the elements of the diagonal, which is passed by reference.
*/
static void diagPrintUtil(__nod root,int d,
TreeMap<Integer,Vector<Integer>> diagPrint)
{
// writing the basic case.
if (root == NILL)
return;
//Now, we will store all the nodes of the same line together, and that too in a vector.
Vector<Integer> k = diagPrint.get(d);
// we know that the value K is NILL, so we have to create a vector and store all the records in the same.
if (k == NILL)
{
k = new Vector<>();
k.add(root.record);
}
// If the value K is not NILL, then we have to update the list, or else
else
{
k.add(root.record);
}
diagPrint.put(d,k);
// We have to increment the vertical distance if the left child is: -
diagPrintUtil(root.Lft,
d + 1, diagPrint);
// the vertical distance from the right child will remain the same.
diagPrintUtil(root.Rt,
d, diagPrint);
}
// Now, start printing the diagonal traversal of the given binary tree.
static void diagPrint(__nod root)
{
// Now, we will start by creating the map of all the vectors and will be able to store all the elements provided by the diagonals.
TreeMap<Integer,Vector<Integer>>
diagPrint = new TreeMap<>();
diagPrintUtil(root, 0, diagPrint);
System.out.println("Diagonal Traversal of Binary Tree");
for (Entry<Integer, Vector<Integer>> entry :
diagPrint.entrySet())
{
System.out.println(entry.getValue());
}
}
// writing the main program to test the above functions.
public static void main(String[] args)
{
__nod root = new __nod(8);
root.Lft = new __nod(3);
root.Rt = new __nod(10);
root.Lft.Lft = new __nod(1);
root.Lft.Rt = new __nod(6);
root.Rt.Rt = new __nod(14);
root.Rt.Rt.Lft = new __nod(13);
root.Lft.Rt.Lft = new __nod(4);
root.Lft.Rt.Rt = new __nod(7);
diagPrint(root);
}
}
Output:
Example 4
#include <bits/stdc++.h>
using namespace std;
// creating a new tree node
struct __nod {
int record;
__nod *Lft, *Rt;
};
vector<int> diagonal(__nod* root)
{
vector<int> diagonalVals;
if (!root)
return diagonalVals;
// The LeftQueue will be a queue and store all the left pointers while traversing the tree, and it will be utilized when at any given pointer at the right, it becomes NILL.
queue<__nod*> LftQueue;
__nod* __nod = root;
while (__nod) {
// We have added the current node to the output.
diagonalVals.push_back(__nod->record);
// If the left child is available, we must add it to the queue.
if (__nod->Lft)
LftQueue.push(__nod->Lft);
// If there is a right child, we must transfer the node to the right.
if (__nod->Rt)
__nod = __nod->Rt;
else {
// If the child is present at the left, then the queue is not empty, and we have to utilize it to traverse further and transmit.
if (!LftQueue.empty()) {
__nod = LftQueue.front();
LftQueue.pop();
}
else {
// after this, all the child on the right will be traversed, and none of the left child will be there.
__nod = NILL;
}
}
}
return diagonalVals;
}
// creating a utility method to create a new node.
__nod* new__nod(int record)
{
__nod* __nod = new __nod;
__nod->record = record;
__nod->Lft = __nod->Rt = NILL;
return __nod;
}
// writing the main program
int main()
{
__nod* root = new__nod(8);
root->Lft = new__nod(3);
root->Rt = new__nod(10);
root->Lft->Lft = new__nod(1);
root->Lft->Rt = new__nod(6);
root->Rt->Rt = new__nod(14);
root->Rt->Rt->Lft = new__nod(13);
root->Lft->Rt->Lft = new__nod(4);
root->Lft->Rt->Rt = new__nod(7);
/* __nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(9);
root->Lft->Rt = new__nod(6);
root->Rt->Lft = new__nod(4);
root->Rt->Rt = new__nod(5);
root->Rt->Lft->Rt = new__nod(7);
root->Rt->Lft->Lft = new__nod(12);
root->Lft->Rt->Lft = new__nod(11);
root->Lft->Lft->Rt = new__nod(10);*/
vector<int> diagonalValues = diagonal(root);
for (int i = 0; i < diagonalValues.size(); i++) {
cout << diagonalValues[i] << " ";
}
cout << endl;
return 0;
}
Output:
Example 5
//Write down the main Java program to check the implementation of the diagonal traversal of the binary tree.
import java.util.*;
// creating a new tree node
class __nod {
int record;
__nod Lft, Rt;
};
class BinaryTree {
public static List<Integer> diagonal(__nod root)
{
List<Integer> diagonalVals = new ArrayList<>();
if (root == NILL)
return diagonalVals;
// The LeftQueue will be a queue and store all the left pointers while traversing the tree, and it will be utilized when at any given pointer at the right, it becomes NILL.
Queue<__nod> LftQueue = new LinkedList<>();
__nod __nod = root;
while (__nod != NILL) {
// We have added the current node to the output.
diagonalVals.add(__nod.record);
// If the left child is available, we must add it to the queue.
if (__nod.Lft != NILL)
LftQueue.add(__nod.Lft);
// If there is a right child, we must transfer the node to the right.
if (__nod.Rt != NILL)
__nod = __nod.Rt;
else {
// If the child is present at the left, then the queue is not empty, and we have to utilize it to traverse further and transmit.
if (!LftQueue.isEmpty()) {
__nod = LftQueue.peek();
LftQueue.remove();
}
else {
// after this, all the child on the right will be traversed, and none of the left child will be there.
__nod = NILL;
}
}
}
return diagonalVals;
}
// creating a utility method to create a new node.
public static __nod new__nod(int record)
{
__nod __nod = new __nod();
__nod.record = record;
__nod.Lft = __nod.Rt = NILL;
return __nod;
}
// writing the main program
public static void main(String[] args)
{
__nod root = new__nod(8);
root.Lft = new__nod(3);
root.Rt = new__nod(10);
root.Lft.Lft = new__nod(1);
root.Lft.Rt = new__nod(6);
root.Rt.Rt = new__nod(14);
root.Rt.Rt.Lft = new__nod(13);
root.Lft.Rt.Lft = new__nod(4);
root.Lft.Rt.Rt = new__nod(7);
/* __nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(9);
root->Lft->Rt = new__nod(6);
root->Rt->Lft = new__nod(4);
root->Rt->Rt = new__nod(5);
root->Rt->Lft->Rt = new__nod(7);
root->Rt->Lft->Lft = new__nod(12);
root->Lft->Rt->Lft = new__nod(11);
root->Lft->Lft->Rt = new__nod(10);*/
List<Integer> diagonalValues = diagonal(root);
for (int i = 0; i < diagonalValues.size(); i++) {
System.out.print(diagonalValues.get(i) + " ");
}
System.out.println();
}
}
Output:
Example 6
from collections import deque
# creating a binary tree node
class __nod:
# creating a new constructor to create a binary tree node.
def __init__(self, record):
self.record = record
self.Lft = None
self.Rt = None
def diagonal(root):
out = []
__nod = root
# queue that will store the nodes at the left
Lft_q = deque()
while __nod:
# transmit the record to the output array
out.append(__nod.record)
# if the left is available, we have to send it to the array
if __nod.Lft:
Lft_q.appendLft(__nod.Lft)
# if the right is available, we have to change the nodes.
if __nod.Rt:
__nod = __nod.Rt
else:
# otherwise, we can pop out the left q.
if len(Lft_q) >= 1:
__nod = Lft_q.pop()
else:
__nod = None
return out
# writing the main code
root = __nod(8)
root.Lft = __nod(3)
root.Rt = __nod(10)
root.Lft.Lft = __nod(1)
root.Lft.Rt = __nod(6)
root.Rt.Rt = __nod(14)
root.Rt.Rt.Lft = __nod(13)
root.Lft.Rt.Lft = __nod(4)
root.Lft.Rt.Rt = __nod(7)
print(diagonal(root))
Output:
