Tutorialspoint.dev

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 same line.

Input : Root of below tree
 

Output : 
Diagonal Traversal of binary tree : 
 8 10 14
 3 6 7 13
 1 4



We have discussed recursive solution in below post.

Diagonal Traversal of Binary Tree

In this post, iterative solution is discussed. The idea is to use a queue to store only the left child of current node. After printing the data of current node make the current node to its right child, if present.
A delimiter NULL is used to mark the starting of next diagonal.

Below is the implementation of above approach.

C++

/* C++ program to construct string from binary tree*/
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to left
   child and a pointer to right child */
struct Node {
    int data;
    Node *left, *right;
};
  
/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
  
// Iterative function to print diagonal view
void diagonalPrint(Node* root)
{
    // base case
    if (root == NULL)
        return;
  
    // inbuilt queue of Treenode
    queue<Node*> q;
  
    // push root
    q.push(root);
  
    // push delimiter
    q.push(NULL);
  
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
  
        // if current is delimiter then insert another
        // for next diagonal and cout nextline
        if (temp == NULL) {
  
            // if queue is empty return
            if (q.empty())
                return;
  
            // output nextline
            cout << endl;
  
            // push delimiter again
            q.push(NULL);
        }
        else {
            while (temp) {
                cout << temp->data << " ";
  
                // if left child is present 
                // push into queue
                if (temp->left)
                    q.push(temp->left);
  
                // current equals to right child
                temp = temp->right;
            }
        }
    }
}
  
// Driver Code
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);
}

Java

// Java program to con string from binary tree
import java.util.*;
class solution
{
  
    
// A binary tree node has data, pointer to left 
 //  child and a pointer to right child 
static class Node { 
    int data; 
    Node left, right; 
}; 
    
// Helper function that allocates a new node 
static Node newNode(int data) 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null
    return (node); 
    
// Iterative function to print diagonal view 
static void diagonalPrint(Node root) 
    // base case 
    if (root == null
        return
    
    // inbuilt queue of Treenode 
    Queue<Node> q= new LinkedList<Node>(); 
    
    // add root 
    q.add(root); 
    
    // add delimiter 
    q.add(null); 
    
    while (q.size()>0) { 
        Node temp = q.peek(); 
        q.remove(); 
    
        // if current is delimiter then insert another 
        // for next diagonal and cout nextline 
        if (temp == null) { 
    
            // if queue is empty return 
            if (q.size()==0
                return
    
            // output nextline 
            System.out.println();
    
            // add delimiter again 
            q.add(null); 
        
        else
            while (temp!=null) { 
                System.out.print( temp.data + " "); 
    
                // if left child is present  
                // add into queue 
                if (temp.left!=null
                    q.add(temp.left); 
    
                // current equals to right child 
                temp = temp.right; 
            
        
    
    
// Driver Code 
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); 
    diagonalPrint(root); 
}
//contributed by Arnab Kundu

C#

// C# program to con string from binary tree
using System; 
using System.Collections;
  
class GFG
{
  
// A binary tree node has data, 
// pointer to left child and
// a pointer to right child 
public class Node
    public int data; 
    public Node left, right; 
}; 
      
// Helper function that
// allocates a new node 
static Node newNode(int data) 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null
    return (node); 
      
// Iterative function to print diagonal view 
static void diagonalPrint(Node root) 
    // base case 
    if (root == null
        return
      
    // inbuilt queue of Treenode 
    Queue q = new Queue(); 
      
    // Enqueue root 
    q.Enqueue(root); 
      
    // Enqueue delimiter 
    q.Enqueue(null); 
      
    while (q.Count > 0) 
    
        Node temp = (Node) q.Peek(); 
        q.Dequeue(); 
      
        // if current is delimiter then insert another 
        // for next diagonal and cout nextline 
        if (temp == null
        
      
            // if queue is empty return 
            if (q.Count == 0) 
                return
      
            // output nextline 
            Console.WriteLine();
      
            // Enqueue delimiter again 
            q.Enqueue(null); 
        
        else 
        
            while (temp != null)
            
                Console.Write( temp.data + " "); 
      
                // if left child is present 
                // Enqueue into queue 
                if (temp.left != null
                    q.Enqueue(temp.left); 
      
                // current equals to right child 
                temp = temp.right; 
            
        
    
      
// Driver Code 
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); 
    diagonalPrint(root); 
}
  
// This code is contributed by Arnab Kundu


Output:

8 10 14 
3 6 7 13 
1 4


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter