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