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 treeOutput : 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
leave a comment
0 Comments