Diagonal Traversal of Binary Tree

Last Updated : 07 Aug, 2023

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

unnamed

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 node
struct 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 tree
void 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 node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Driver program
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);
 
    /*  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 Tree
import 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 node
class 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 tree
def 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 Tree
class 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 node
struct 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 node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Driver program
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);
 
    /* 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 approach
import java.util.*;
 
// Tree node
class 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 node
 
 
class Node:
 
    # Constructor to create a
    # new binary tree node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def 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 Code
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)
 
print(diagonal(root))

C#

// C# Code for above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
// Tree node
class 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 node
class 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 node
function newNode(data){
    node = new Node(data);
    return node;
}
 
// Driver program
let 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 Node
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
 
 
def 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 approach
 
using 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 node
class 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 code
let 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.

A

Aditya Goel

Improve

Previous Article

Iterative Postorder Traversal | Set 1 (Using Two Stacks)

Boundary Traversal of binary tree

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Kth node in Diagonal Traversal of Binary Tree

Given a binary tree and a value K. The task is to print the k-th node in the diagonal traversal of the binary tree. If no such node exists then print -1.Examples: Input : 8 / \ 3 10 / / \ 1 6 14 / \ / 4 7 13 k = 5 Output : 6 Diagonal Traversal of the above tree is: 8 10 14 3 6 7 13 1 4 Input : 1 / \ 2 3 / \ 4 5 k = 7 Output : -1 Approach: The idea

Iterative diagonal traversal of binary tree

Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to the same line. Input : Root of below tree Output : Diagonal Traversal of binary tree : 8 10 14 3 6 7 13 1 4Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. We have discussed the recursiv

Level order traversal of Binary Tree using Morris Traversal

Given a binary tree, the task is to traverse the Binary Tree in level order fashion.Examples: Input: 1 / \ 2 3 Output: 1 2 3 Input: 5 / \ 2 3 \ 6 Output: 5 2 3 6 Approach: The idea is to use Morris Preorder Traversal to traverse the tree in level order traversal.Observations: There are mainly two observations for the traversal of the tree using Mor

Pre Order, Post Order and In Order traversal of a Binary Tree in one traversal | (Using recursion)

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order in one iteration. Examples: Input: Output: Pre Order: 1 2 4 5 3 6 7 Post Order: 4 5 2 6 7 3 1 In Order: 4 2 5 1 6 3 7 Input: Output: Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11 Post Order: 12 8 4 9 5 2 6 10 11 7 3 1 In Order: 8 12 4 2 9 5 1 6

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Filling diagonal to make the sum of every row, column and diagonal equal of 3x3 matrix

Given 9 elements in a 3 x 3 matrix where the value of diagonals is 0. We need to find the values in the diagonal to make the sum of every row, column, and diagonal equal. Examples: Input: 0 3 6 5 0 5 4 7 0 Output: 6 3 6 5 5 5 4 7 4 Explanation: Now the value of the sum of any row or column is 15 Input: 0 4 4 4 0 4 4 4 0 Output: 4 4 4 4 4 4 4 4 4 Ap

Length of a Diagonal of a Parallelogram using the length of Sides and the other Diagonal

Given two integers A and B, denoting the length of a parallelogram and an integer D, denoting the length of a diagonal, the task is to find the length of another diagonal of the parallelogram. Examples: Input: A = 10, B = 30, D = 20Output: 40.0 Input: A = 6, B = 8, D = 10Output: 10.0 Approach: The relation between sides and diagonals of a parallelo

Maximum sum of elements in a diagonal parallel to the main diagonal of a given Matrix

Give a square matrix mat[][] of dimensions N * N, the task is to find the maximum sum of elements present in the given matrix along the diagonals which are parallel to the main diagonal. Below is the image of the same. Examples: Input: mat[][] = {{1, 2, 5, 7}, {2, 6, 7, 3}, {12, 3, 2, 4}, {3, 6, 9, 4}}Output: 18Explanation:Sum of elements present i

Program to swap upper diagonal elements with lower diagonal elements of matrix.

Given a square matrix, swap upper diagonal elements of matrix with lower diagonal elements of matrix. Examples : Input: 2 3 5 6 4 5 7 9 8 6 4 9 1 3 5 6 Output: 2 4 8 1 3 5 6 3 5 7 4 5 6 9 9 6 Input: 1 2 3 4 5 6 7 8 9 Output: 1 4 7 2 5 8 3 6 9Recommended PracticeSwapping TrianglesTry It! Below is the implementation of above idea : C/C++ Code // CPP

Article Tags :

Practice Tags :