fork(1) download
copy 
  1. // Time Complexity : O(n)
  2. // Space Complexity : O(n)
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <queue>
  7. #include <map>
  8. using namespace std;
  9.  
  10. // Data structure to store a Binary Tree node
  11. struct Node
  12. {
  13. 	int key;
  14. 	Node *left, *right;
  15. };
  16.  
  17. // Function to create a new binary tree node having given key
  18. Node* newNode(int key)
  19. {
  20. 	Node* node = new Node;
  21. 	node->key = key;
  22. 	node->left = node->right = nullptr;
  23.  
  24. 	return node;
  25. }
  26.  
  27. // Function to insert given key into the tree
  28. void insert(Node*& root, string level, int key)
  29. {
  30. 	// tree is empty
  31. 	if (level.length() == 0)
  32. 	{
  33. 		root = newNode(key);
  34. 		return;
  35. 	}
  36.  
  37. 	int i = 0;
  38. 	Node* ptr = root;
  39. 	while (i < level.length() - 1)
  40. 	{
  41. 		if (level[i++] == 'L')
  42. 			ptr = ptr->left;
  43. 		else
  44. 			ptr = ptr->right;
  45. 	}
  46.  
  47. 	if (level[i] == 'L')
  48. 		ptr->left = newNode(key);
  49. 	else
  50. 		ptr->right = newNode(key);
  51. }
  52.  
  53. // Function to print all nodes of a given binary tree in specific
  54. // order from top to bottom
  55. void printNodes(Node* root)
  56. {
  57.     // return is tree is empty
  58. 	if (root == nullptr)
  59. 		return;
  60.  
  61.     // start with level 1 (of root node)
  62. 	int level = 1;
  63.  
  64. 	// create an empty multi-map of integers (every key can be
  65.     // associated with multiple values)
  66.     map<int, vector<int>> map;
  67.  
  68.     // insert root node at first level
  69. 	map[level].push_back(root->key);
  70.  
  71.     // create an empty queue and enqueue root's left and
  72.     // right child respectively
  73. 	queue<Node *> Q;
  74.  
  75. 	if(root->left && root->right)
  76. 	{
  77. 		Q.push(root->left);
  78. 		Q.push(root->right);
  79. 	}
  80.  
  81.     // run till queue is not empty
  82. 	while (!Q.empty())
  83. 	{
  84. 		// increment level by 1
  85. 		level++;
  86.  
  87. 		// calculate number of nodes in current level
  88. 		int n = Q.size();
  89.  
  90. 		while (n)
  91. 		{
  92. 			// pop first two nodes from queue and insert them into the map
  93. 			Node* x = Q.front();
  94. 			Q.pop();
  95.  
  96. 			Node* y = Q.front();
  97. 		    Q.pop();
  98.  
  99. 			map[level].push_back(x->key);
  100. 			map[level].push_back(y->key);
  101.  
  102. 			// In each iteration enqueue x->left, y->right then x->right, y->left 
  103. 			if (x->left)
  104. 				Q.push(x->left);
  105.  
  106. 			if (y->right)
  107. 				Q.push(y->right);
  108.  
  109. 			if (x->right)
  110. 				Q.push(x->right);
  111.  
  112. 			if (y->left)
  113. 				Q.push(y->left);
  114.  
  115. 			n = n - 2;
  116. 		}
  117. 	}
  118.  
  119.     // iterate through the map using reverse iterator and
  120. 	// print all nodes present in very level
  121. 	for (auto it = map.rbegin(); it != map.rend(); it++)
  122. 	{
  123. 		for (int i: it->second)
  124. 			cout << i << " ";
  125. 	}
  126. }
  127.  
  128. // main function
  129. int main()
  130. {
  131. 	Node* root = nullptr;
  132. 	vector<pair<string, int> > keys =
  133. 	{
  134. 		{"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"LR", 5}, {"RL", 6},
  135. 		{"RR", 7}, {"LLL", 8}, {"LLR", 9}, {"LRL", 10}, {"LRR", 11},
  136. 		{"RLL", 12}, {"RLR", 13}, {"RRL", 14}, {"RRR", 15}
  137. 	};
  138.  
  139. 	for (auto pair: keys)
  140. 		insert(root, pair.first, pair.second);
  141.  
  142. 	printNodes(root);
  143.  
  144. 	return 0;
  145. }
  146.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8 15 9 14 10 13 11 12 4 7 5 6 2 3 1
https://ideone.com/nuUNJr
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!