fork download 
  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. // Recursive function to do a pre-order traversal of the tree and
  48. // fill the map with diagonal elements
  49. void printDiagonal(Node *node, int diagonal, auto &map)
  50. {
  51. 	// base case: empty tree
  52. 	if (node == nullptr)
  53. 		return;
  54.  
  55.     // insert current node in current diagonal
  56. 	map.insert(make_pair(diagonal, node->data));
  57.  
  58. 	// recurse for left subtree by increasing diagonal by 1
  59.     printDiagonal(node->left, diagonal + 1, map);
  60.  
  61. 	// recurse for right subtree with same diagonal
  62. 	printDiagonal(node->right, diagonal, map);
  63. }
  64.  
  65. // Function to print the diagonal elements of given binary tree
  66. void printDiagonal(Node *root)
  67. {
  68. 	// create an empty map to store diagonal element in every slope
  69. 	// we can also use map<int, vector<int>> instead of multimap<int, int>
  70. 	multimap<int, int> map;
  71.  
  72.  
  73.     // do pre-order traversal of the tree and fill the map
  74. 	printDiagonal(root, 0, map);
  75.  
  76. 	// traverse the map and print diagonal elements
  77.    	int temp = 0;
  78.  	for (auto it = map.begin(); it != map.end(); it++)
  79. 	{
  80. 		if (temp != it->first)
  81.    		{
  82.    			cout << endl;
  83.    			temp = it->first;
  84.    		}
  85. 		cout << it->second << " ";
  86.  	}
  87. }
  88.  
  89. // main function
  90. int main()
  91. {
  92.     /* Construct below tree
  93.           1
  94.         /   \
  95.        /     \
  96.       2       3
  97.      /      /  \
  98.     /      /    \
  99.    4      5      6
  100.          / \
  101.         /   \
  102.        7     8
  103.     */
  104.  
  105. 	vector<pair<string, int> > keys =
  106. 	{
  107. 		 {"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"RL", 5},
  108. 		 {"RR", 6}, {"RLL", 7}, {"RLR", 8}
  109. 	};
  110.  
  111. 	Node* root = nullptr;
  112.  
  113. 	for (auto pair: keys)
  114. 		insert(root, pair.first, pair.second);
  115.  
  116. 	printDiagonal(root);
  117.  
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0s 4508KB
comments (?)
stdin 
Standard input is empty
stdout 
1 3 6 
2 5 8 
4 7
https://ideone.com/2gcfIL
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!