fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Data structure to store a Binary Tree node
  5. struct Node
  6. {
  7. 	int data;
  8. 	Node *left, *right;
  9. };
  10.  
  11. // Function to create a new binary tree node having given key
  12. Node* newNode(int key)
  13. {
  14. 	Node* node = new Node;
  15. 	node->data = key;
  16. 	node->left = node->right = nullptr;
  17.  
  18. 	return node;
  19. }
  20.  
  21. // Function to insert given key into the tree
  22. void insert(Node*& root, string level, int key)
  23. {
  24. 	// tree is empty
  25. 	if (level.length() == 0)
  26. 	{
  27. 		root = newNode(key);
  28. 		return;
  29. 	}
  30.  
  31. 	int i = 0;
  32. 	Node* ptr = root;
  33. 	while (i < level.length() - 1)
  34. 	{
  35. 		if (level[i++] == 'L')
  36. 			ptr = ptr->left;
  37. 		else
  38. 			ptr = ptr->right;
  39. 	}
  40.  
  41. 	if (level[i] == 'L')
  42. 		ptr->left = newNode(key);
  43. 	else
  44. 		ptr->right = newNode(key);
  45. }
  46.  
  47. // Iterative function to print the diagonal elements of given binary tree
  48. void diagonalPrint(Node* root)
  49. {
  50. 	// create an empty queue
  51. 	queue<Node*> q;
  52.  
  53. 	// create a sentinel (dummy) node to denote end of a diagonal
  54. 	Node* sentinel = newNode(-1);
  55.  
  56. 	// enqueue all nodes of first diagonal in binary tree
  57. 	while (root)
  58. 	{
  59. 		q.push(root);
  60. 		root = root->right;
  61. 	}
  62.  
  63. 	// enqueue sentinel node at the end of each diagonal
  64. 	q.push(sentinel);
  65.  
  66. 	// run till only sentinel is left
  67. 	while (q.size() != 1)
  68. 	{
  69. 		// dequeue front node
  70. 		Node* front = q.front();
  71. 		q.pop();
  72.  
  73. 		if (front != sentinel)
  74. 		{
  75. 			// print current node
  76. 			cout << front->data << " ";
  77.  
  78. 			// enqueue nodes of next diagonal in binary tree
  79. 			Node* node = front->left;
  80. 			while (node)
  81. 			{
  82. 				q.push(node);
  83. 				node = node->right;
  84. 			}
  85. 		}
  86. 		else
  87. 		{
  88. 			// if end of current diagonal is reached, enqueue sentinel node
  89. 			// and print newline
  90. 			q.push(sentinel);
  91. 			cout << endl;
  92. 		}
  93. 	}
  94. }
  95.  
  96. // main function
  97. int main()
  98. {
  99.     /* Construct below tree
  100.           1
  101.         /   \
  102.        /     \
  103.       2       3
  104.      /      /  \
  105.     /      /    \
  106.    4      5      6
  107.          / \
  108.         /   \
  109.        7     8
  110.     */
  111.  
  112. 	vector<pair<string, int> > keys =
  113. 	{
  114. 		 {"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"RL", 5},
  115. 		 {"RR", 6}, {"RLL", 7}, {"RLR", 8}
  116. 	};
  117.  
  118. 	Node* root = nullptr;
  119.  
  120. 	for (auto pair: keys)
  121. 		insert(root, pair.first, pair.second);
  122.  
  123. 	diagonalPrint(root);
  124.  
  125. 	return 0;
  126. }
  127.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 3 6 
2 5 8 
4 7
https://ideone.com/8vvGc5
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!