Consider lines with a slope of -1 that cross through nodes. Print all diagonal elements in a binary tree that belong to the same line, given a binary tree.
Input : Root of below tree
Output :
Diagonal Traversal of binary tree:
8 10 14
3 6 7 13
1 4
Observation : root and root->right values will be prioritized over all root->left values.
The plan is to make use of a map. Different slope distances are used in the map as a key. The map’s value is a node vector (or dynamic array). To save values in the map, we traverse the tree. We print the contents of the map after it has been constructed.
Below is the implementation of the above idea.
C++
// C++ program for diagonal // traversal of Binary Tree#include <bits/stdc++.h>using namespace std;// Tree nodestruct Node{ int data; Node *left, *right;};/* root - root of the binary tree d - distance of current line from rightmost -topmost slope. diagonalPrint - multimap to store Diagonal elements (Passed by Reference) */void diagonalPrintUtil(Node* root, int d, map<int, vector<int>> &diagonalPrint){ // Base case if (!root) return; // Store all nodes of same // line together as a vector diagonalPrint[d].push_back(root->data); // Increase the vertical // distance if left child diagonalPrintUtil(root->left, d + 1, diagonalPrint); // Vertical distance remains // same for right child diagonalPrintUtil(root->right, d, diagonalPrint);}// Print diagonal traversal // of given binary treevoid diagonalPrint(Node* root){ // create a map of vectors // to store Diagonal elements map<int, vector<int> > diagonalPrint; diagonalPrintUtil(root, 0, diagonalPrint); cout << "Diagonal Traversal of binary tree : \n"; for (auto it :diagonalPrint) { vector<int> v=it.second; for(auto it:v) cout<<it<<" "; cout<<endl; }}// Utility method to create a new nodeNode* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return node;}// Driver programint main(){ Node* root = newNode(8); root->left = newNode(3); root->right = newNode(10); root->left->left = newNode(1); root->left->right = newNode(6); root->right->right = newNode(14); root->right->right->left = newNode(13); root->left->right->left = newNode(4); root->left->right->right = newNode(7); /* Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(9); root->left->right = newNode(6); root->right->left = newNode(4); root->right->right = newNode(5); root->right->left->right = newNode(7); root->right->left->left = newNode(12); root->left->right->left = newNode(11); root->left->left->right = newNode(10);*/ diagonalPrint(root); return 0;} |
Java
// Java program for diagonal // traversal of Binary Treeimport java.util.TreeMap;import java.util.Map.Entry;import java.util.Vector;public class DiagonalTraversalBTree { // Tree node static class Node { int data; Node left; Node right; //constructor Node(int data) { this.data=data; left = null; right =null; } } /* root - root of the binary tree d - distance of current line from rightmost -topmost slope. diagonalPrint - HashMap to store Diagonal elements (Passed by Reference) */ static void diagonalPrintUtil(Node root,int d, TreeMap<Integer,Vector<Integer>> diagonalPrint) { // Base case if (root == null) return; // get the list at the particular d value Vector<Integer> k = diagonalPrint.get(d); // k is null then create a // vector and store the data if (k == null) { k = new Vector<>(); k.add(root.data); } // k is not null then update the list else { k.add(root.data); } // Store all nodes of same line // together as a vector diagonalPrint.put(d,k); // Increase the vertical distance // if left child diagonalPrintUtil(root.left, d + 1, diagonalPrint); // Vertical distance remains // same for right child diagonalPrintUtil(root.right, d, diagonalPrint); } // Print diagonal traversal // of given binary tree static void diagonalPrint(Node root) { // create a map of vectors // to store Diagonal elements TreeMap<Integer,Vector<Integer>> diagonalPrint = new TreeMap<>(); diagonalPrintUtil(root, 0, diagonalPrint); System.out.println("Diagonal Traversal of Binary Tree"); for (Entry<Integer, Vector<Integer>> entry : diagonalPrint.entrySet()) { System.out.println(entry.getValue()); } } // Driver program public static void main(String[] args) { Node root = new Node(8); root.left = new Node(3); root.right = new Node(10); root.left.left = new Node(1); root.left.right = new Node(6); root.right.right = new Node(14); root.right.right.left = new Node(13); root.left.right.left = new Node(4); root.left.right.right = new Node(7); diagonalPrint(root); }}// This code is contributed by Sumit Ghosh |
Python3
# Python program for diagonal # traversal of Binary Tree# A binary tree nodeclass Node: # Constructor to create a # new binary tree node def __init__(self, data): self.data = data self.left = None self.right = None""" root - root of the binary tree d - distance of current line from rightmost -topmost slope. diagonalPrint - multimap to store Diagonal elements (Passed by Reference) """def diagonalPrintUtil(root, d, diagonalPrintMap): # Base Case if root is None: return # Store all nodes of same line # together as a vector try : diagonalPrintMap[d].append(root.data) except KeyError: diagonalPrintMap[d] = [root.data] # Increase the vertical distance # if left child diagonalPrintUtil(root.left, d+1, diagonalPrintMap) # Vertical distance remains # same for right child diagonalPrintUtil(root.right, d, diagonalPrintMap)# Print diagonal traversal of given binary treedef diagonalPrint(root): # Create a dict to store diagonal elements diagonalPrintMap = dict() # Find the diagonal traversal diagonalPrintUtil(root, 0, diagonalPrintMap) print ("Diagonal Traversal of binary tree : ") for i in diagonalPrintMap: for j in diagonalPrintMap[i]: print (j,end=" ") print()# Driver Program root = Node(8)root.left = Node(3)root.right = Node(10)root.left.left = Node(1)root.left.right = Node(6)root.right.right = Node(14)root.right.right.left = Node(13)root.left.right.left = Node(4)root.left.right.right = Node(7)diagonalPrint(root)# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System;using System.Collections.Generic;class Node{ public int data; public Node left; public Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; }}class BinaryTree{ public static void diagonalPrintUtil(Node root, int d, Dictionary<int, List<int>> diagonalPrint) { if (root == null) return; if (!diagonalPrint.ContainsKey(d)) { diagonalPrint[d] = new List<int>(); } diagonalPrint[d].Add(root.data); diagonalPrintUtil(root.left, d + 1, diagonalPrint); diagonalPrintUtil(root.right, d, diagonalPrint); } public static void diagonalPrint(Node root) { Dictionary<int, List<int>> diagonalPrint = new Dictionary<int, List<int>>(); diagonalPrintUtil(root, 0, diagonalPrint); Console.WriteLine("Diagonal Traversal of Binary Tree"); foreach (KeyValuePair<int, List<int>> entry in diagonalPrint) { Console.WriteLine(string.Join(" ", entry.Value)); } } public static void Main(string[] args) { Node root = new Node(8); root.left = new Node(3); root.right = new Node(10); root.left.left = new Node(1); root.left.right = new Node(6); root.right.right = new Node(14); root.right.right.left = new Node(13); root.left.right.left = new Node(4); root.left.right.right = new Node(7); diagonalPrint(root); }} |
Javascript
//Javascript program for diagonal //traversal of Binary Treeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}function diagonalPrintUtil(root, d, diagonalPrint = new Map()) { if (!root) return; let k = diagonalPrint.get(d) || []; k.push(root.data); diagonalPrint.set(d, k); diagonalPrintUtil(root.left, d + 1, diagonalPrint); diagonalPrintUtil(root.right, d, diagonalPrint);}function diagonalPrint(root) { const diagonalPrint = new Map(); diagonalPrintUtil(root, 0, diagonalPrint); console.log("Diagonal Traversal of Binary Tree"); for (const [key, value] of diagonalPrint) { console.log(value); }}const root = new Node(8);root.left = new Node(3);root.right = new Node(10);root.left.left = new Node(1);root.left.right = new Node(6);root.right.right = new Node(14);root.right.right.left = new Node(13);root.left.right.left = new Node(4);root.left.right.right = new Node(7);diagonalPrint(root);// This code is contributed by shivamsharma215 |
Output
Diagonal Traversal of binary tree : 8 10 14 3 6 7 13 1 4
Time complexity: O( N logN )
Auxiliary Space: O( N )
The identical problem may be solved with a queue and an iterative method.
C++14
#include <bits/stdc++.h>using namespace std;// Tree nodestruct Node { int data; Node *left, *right;};vector<int> diagonal(Node* root){ vector<int> diagonalVals; if (!root) return diagonalVals; // The leftQueue will be a queue which will store all // left pointers while traversing the tree, and will be // utilized when at any point right pointer becomes NULL queue<Node*> leftQueue; Node* node = root; while (node) { // Add current node to output diagonalVals.push_back(node->data); // If left child available, add it to queue if (node->left) leftQueue.push(node->left); // if right child, transfer the node to right if (node->right) node = node->right; else { // If left child Queue is not empty, utilize it // to traverse further if (!leftQueue.empty()) { node = leftQueue.front(); leftQueue.pop(); } else { // All the right childs traversed and no // left child left node = NULL; } } } return diagonalVals;}// Utility method to create a new nodeNode* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return node;}// Driver programint main(){ Node* root = newNode(8); root->left = newNode(3); root->right = newNode(10); root->left->left = newNode(1); root->left->right = newNode(6); root->right->right = newNode(14); root->right->right->left = newNode(13); root->left->right->left = newNode(4); root->left->right->right = newNode(7); /* Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(9); root->left->right = newNode(6); root->right->left = newNode(4); root->right->right = newNode(5); root->right->left->right = newNode(7); root->right->left->left = newNode(12); root->left->right->left = newNode(11); root->left->left->right = newNode(10);*/ vector<int> diagonalValues = diagonal(root); for (int i = 0; i < diagonalValues.size(); i++) { cout << diagonalValues[i] << " "; } cout << endl; return 0;} |
Java
// Java Code for above approachimport java.util.*;// Tree nodeclass Node { int data; Node left, right;};class BinaryTree { public static List<Integer> diagonal(Node root) { List<Integer> diagonalVals = new ArrayList<>(); if (root == null) return diagonalVals; // The leftQueue will be a queue which will store // all left pointers while traversing the tree, and // will be utilized when at any point right pointer // becomes NULL Queue<Node> leftQueue = new LinkedList<>(); Node node = root; while (node != null) { // Add current node to output diagonalVals.add(node.data); // If left child available, add it to queue if (node.left != null) leftQueue.add(node.left); // if right child, transfer the node to right if (node.right != null) node = node.right; else { // If left child Queue is not empty, utilize // it to traverse further if (!leftQueue.isEmpty()) { node = leftQueue.peek(); leftQueue.remove(); } else { // All the right childs traversed and no // left child left node = null; } } } return diagonalVals; } // Utility method to create a new node public static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return node; } // Driver program public static void main(String[] args) { Node root = newNode(8); root.left = newNode(3); root.right = newNode(10); root.left.left = newNode(1); root.left.right = newNode(6); root.right.right = newNode(14); root.right.right.left = newNode(13); root.left.right.left = newNode(4); root.left.right.right = newNode(7); /* Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(9); root->left->right = newNode(6); root->right->left = newNode(4); root->right->right = newNode(5); root->right->left->right = newNode(7); root->right->left->left = newNode(12); root->left->right->left = newNode(11); root->left->left->right = newNode(10);*/ List<Integer> diagonalValues = diagonal(root); for (int i = 0; i < diagonalValues.size(); i++) { System.out.print(diagonalValues.get(i) + " "); } System.out.println(); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
from collections import deque# A binary tree nodeclass Node: # Constructor to create a # new binary tree node def __init__(self, data): self.data = data self.left = None self.right = Nonedef diagonal(root): out = [] node = root # queue to store left nodes left_q = deque() while node: # append data to output array out.append(node.data) # if left available add it to the queue if node.left: left_q.appendleft(node.left) # if right is available change the node if node.right: node = node.right else: # else pop the left_q if len(left_q) >= 1: node = left_q.pop() else: node = None return out# Driver Coderoot = Node(8)root.left = Node(3)root.right = Node(10)root.left.left = Node(1)root.left.right = Node(6)root.right.right = Node(14)root.right.right.left = Node(13)root.left.right.left = Node(4)root.left.right.right = Node(7)print(diagonal(root)) |
C#
// C# Code for above approachusing System;using System.Collections.Generic;using System.Linq;// Tree nodeclass Node { public int data; public Node left, right;}class GFG { public static List<int> Diagonal(Node root) { var diagonalVals = new List<int>(); if (root == null) return diagonalVals; // The leftQueue will be a queue which will store // all left pointers while traversing the tree, and // will be utilized when at any point right pointer // becomes NULL var leftQueue = new Queue<Node>(); Node node = root; while (node != null) { // Add current node to output diagonalVals.Add(node.data); // If left child available, add it to queue if (node.left != null) leftQueue.Enqueue(node.left); // if right child, transfer the node to right if (node.right != null) node = node.right; else { // If left child Queue is not empty, utilize // it to traverse further if (leftQueue.Count > 0) { node = leftQueue.Peek(); leftQueue.Dequeue(); } else { // All the right childs traversed and no // left child left node = null; } } } return diagonalVals; } // Utility method to create a new node public static Node NewNode(int data) { var node = new Node(); node.data = data; node.left = node.right = null; return node; } // Driver program public static void Main(string[] args) { Node root = NewNode(8); root.left = NewNode(3); root.right = NewNode(10); root.left.left = NewNode(1); root.left.right = NewNode(6); root.right.right = NewNode(14); root.right.right.left = NewNode(13); root.left.right.left = NewNode(4); root.left.right.right = NewNode(7); // Node root = NewNode(1); // root.left = NewNode(2); // root.right = NewNode(3); // root.left.left = NewNode(9); // root.left.right = NewNode(6); // root.right.left = NewNode(4); // root.right.right = NewNode(5); // root.right.left.right = NewNode(7); // root.right.left.left = NewNode(12); // root.left.right.left = NewNode(11); // root.left.left.right = NewNode(10); var diagonalValues = Diagonal(root); for (int i = 0; i < diagonalValues.Count; i++) { Console.Write(diagonalValues[i] + " "); } Console.WriteLine(); }} |
Javascript
// JavaScript program for the above approach// Tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}function diagonal(root){ let diagonalVals = []; if(root == null) return diagonalVals; // The leftQueue will be a queue which will store all // left pointers while traversing the tree, and will be // utilized when at any point right pointer becomes NULL let leftQueue = []; let node = root; while(node != null){ // Add current node to output diagonalVals.push(node.data); // if left child available, add it to queue if(node.left != null) leftQueue.push(node.left); // If right child, transfer the node to right if(node.right != null) node = node.right; else{ // if left child queue is not empty, utilize it // to traverse further if(leftQueue.length > 0){ node = leftQueue.shift(); } else{ // All the right childs traversed and so // left child left node = null; } } } return diagonalVals;}// Utility method to create a new nodefunction newNode(data){ node = new Node(data); return node;}// Driver programlet root = newNode(8)root.left = newNode(3)root.right = newNode(10)root.left.left = newNode(1)root.left.right = newNode(6)root.right.right = newNode(14)root.right.right.left = newNode(13)root.left.right.left = newNode(4)root.left.right.right = newNode(7)let diagonalValues = diagonal(root);for(let i = 0; i<diagonalValues.length; i++){ console.log(diagonalValues[i] + " ");}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
[8, 10, 14, 3, 6, 7, 13, 1, 4]
Time complexity: O(N)
Auxiliary Space: O(N)
Approach 2: Using Queue:
Every node will contribute to the formation of the following diagonal. Only when the element’s left is available will we push it into the queue. We’ll process the node and then go to the right.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;struct Node { int data; Node *left, *right;};Node* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return node;}vector<vector<int> > result;void diagonalPrint(Node* root){ if (root == NULL) return; queue<Node*> q; q.push(root); while (!q.empty()) { int size = q.size(); vector<int> answer; while (size--) { Node* temp = q.front(); q.pop(); // traversing each component; while (temp) { answer.push_back(temp->data); if (temp->left) q.push(temp->left); temp = temp->right; } } result.push_back(answer); }}int main(){ Node* root = newNode(8); root->left = newNode(3); root->right = newNode(10); root->left->left = newNode(1); root->left->right = newNode(6); root->right->right = newNode(14); root->right->right->left = newNode(13); root->left->right->left = newNode(4); root->left->right->right = newNode(7); diagonalPrint(root); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) cout << result[i][j] << " "; cout << endl; } return 0;} |
Java
// THIS CODE IS CONTRIBUTED BY KIRTI AGARAWL(KIRTIAGARWAL23121999)import java.util.*;public class GFG { // Tree node static class Node { int data; Node left; Node right; Node(int data) { this.data = data; this.left = null; this.right = null; } } static class TNode { Node node; int level; public TNode(Node n, int l){ this.node = n; this.level = l; } } public static void diagonalPrint(Node root){ if (root == null) return; TreeMap<Integer, List<Integer> > map = new TreeMap<Integer, List<Integer> >(); Queue<TNode> q = new LinkedList<TNode>(); q.add(new TNode(root, 0)); while (!q.isEmpty()) { TNode curr = q.poll(); map.putIfAbsent(curr.level, new ArrayList<>()); map.get(curr.level).add(curr.node.data); if (curr.node.left != null) q.add(new TNode(curr.node.left, curr.level + 1)); if (curr.node.right != null) q.add(new TNode(curr.node.right, curr.level)); } for (Map.Entry<Integer, List<Integer> > entry : map.entrySet()) { int k = entry.getKey(); List<Integer> l = map.get(k); int size = l.size(); for (int i = 0; i < l.size(); i++) { System.out.print(l.get(i)); System.out.print(" "); } System.out.println(""); } return; } // Driver code public static void main(String[] args){ Node root = new Node(8); root.left = new Node(3); root.right = new Node(10); root.left.left = new Node(1); root.left.right = new Node(6); root.right.right = new Node(14); root.right.right.left = new Node(13); root.left.right.left = new Node(4); root.left.right.right = new Node(7); diagonalPrint(root); }} |
Python3
# Python Program to print diagonal traversal using queue# Tree Nodeclass Node: def __init__(self, x): self.data = x self.left = None self.right = Nonedef diagonalPrint(root): if root is None: return q = [] q.append(root) while len(q) > 0: size = len(q) answer = [] while size > 0: temp = q[0] q.pop(0) # traversing each component; while temp is not None: answer.append(temp.data) if temp.left is not None: q.append(temp.left) temp = temp.right size -= 1 result.append(answer)if __name__ == '__main__': root = Node(8) root.left = Node(3) root.right = Node(10) root.left.left = Node(1) root.left.right = Node(6) root.right.right = Node(14) root.right.right.left = Node(13) root.left.right.left = Node(4) root.left.right.right = Node(7) result = [] diagonalPrint(root) for i in range(len(result)): for j in range(len(result[i])): print(result[i][j], end=" ") print()# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = null; right = null; }}class GFG { static List<List<int> > result = new List<List<int> >(); static void printLevelOrder(Node root) { if (root == null) return; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { int size = q.Count; List<int> answer = new List<int>(); while (size-- != 0) { Node temp = q.Dequeue(); // traversing each component; while (temp != null) { answer.Add(temp.data); if (temp.left != null) q.Enqueue(temp.left); temp = temp.right; } } result.Add(answer); } } // Driver code public static void Main() { Node root = new Node(8); root.left = new Node(3); root.right = new Node(10); root.left.left = new Node(1); root.left.right = new Node(6); root.right.right = new Node(14); root.right.right.left = new Node(13); root.left.right.left = new Node(4); root.left.right.right = new Node(7); printLevelOrder(root); for (int i = 0; i < result.Count; i++) { for (int j = 0; j < result[i].Count; j++) { Console.Write(result[i][j]); Console.Write(" "); } Console.WriteLine(); } }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Javascript
// javascript program for the above approach// structure of tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}function newNode(data){ return new Node(data);}let result = []function diagonalPrint(root){ if(root == null) return; q = []; q.push(root); while(q.length > 0){ let size = q.length; answer = []; while(size--){ let temp = q.shift(); // traversing each component while(temp != null){ answer.push(temp.data); if(temp.left != null) q.push(temp.left); temp = temp.right; } } result.push(answer); }}// driver codelet root = newNode(8);root.left = newNode(3);root.right = newNode(10);root.left.left = newNode(1);root.left.right = newNode(6);root.right.right = newNode(14);root.right.right.left = newNode(13);root.left.right.left = newNode(4);root.left.right.right = newNode(7);diagonalPrint(root);for(let i = 0; i < result.length; i++){ for(let j = 0; j < result[i].length; j++){ console.log(result[i][j] + " "); } }// this code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Output
8 10 14 3 6 7 13 1 4
Time Complexity: O(N), because we are visiting nodes once.
Auxiliary Space: O(N), because we are using a queue.
This article is contributed by Aditya Goel. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
