fork(3) download
copy 
  1. // Time Complexity : O(n)
  2. // Space Complexity : O(n)
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. // Data structure to store a Binary Tree node
  10. struct Node
  11. {
  12. 	int key;
  13. 	Node *left, *right;
  14. };
  15.  
  16. // Function to create a new binary tree node having given key
  17. Node* newNode(int key)
  18. {
  19. 	Node* node = new Node;
  20. 	node->key = key;
  21. 	node->left = node->right = nullptr;
  22.  
  23. 	return node;
  24. }
  25.  
  26. // Function to insert given key into the tree
  27. void insert(Node*& root, string level, int key)
  28. {
  29. 	// tree is empty
  30. 	if (level.length() == 0)
  31. 	{
  32. 		root = newNode(key);
  33. 		return;
  34. 	}
  35.  
  36. 	int i = 0;
  37. 	Node* ptr = root;
  38. 	while (i < level.length() - 1)
  39. 	{
  40. 		if (level[i++] == 'L')
  41. 			ptr = ptr->left;
  42. 		else
  43. 			ptr = ptr->right;
  44. 	}
  45.  
  46. 	if (level[i] == 'L')
  47. 		ptr->left = newNode(key);
  48. 	else
  49. 		ptr->right = newNode(key);
  50. }
  51.  
  52. // Function to print all nodes of a given binary tree in specific
  53. // order from top to bottom
  54. void printNodes(Node* root)
  55. {
  56.     // return is tree is empty
  57. 	if (root == nullptr)
  58. 		return;
  59.  
  60.     // print root node
  61. 	cout << root->key << " ";
  62.  
  63.     // create an empty queue and enqueue root's left and
  64.     // right child respectively
  65. 	queue<Node *> Q;
  66.  
  67. 	if(root->left && root->right)
  68. 	{
  69. 		Q.push(root->left);
  70. 		Q.push(root->right);
  71. 	}
  72.  
  73.     // run till queue is not empty
  74. 	while (!Q.empty())
  75. 	{
  76. 		Node* x = Q.front();
  77. 		Q.pop();
  78.  
  79. 		Node* y = Q.front();
  80.         Q.pop();
  81.  
  82. 		cout << x->key << " ";
  83. 		cout << y->key << " ";
  84.  
  85. 		// In each iteration enqueue x->left, y->right then x->right, y->left 
  86. 		if (x->left)
  87. 			Q.push(x->left);
  88.  
  89. 		if (y->right)
  90. 			Q.push(y->right);
  91.  
  92. 		if (x->right)
  93. 			Q.push(x->right);
  94.  
  95. 		if (y->left)
  96. 			Q.push(y->left);
  97. 	}
  98. }
  99.  
  100. // main function
  101. int main()
  102. {
  103. 	Node* root = nullptr;
  104. 	vector<pair<string, int> > keys =
  105. 	{
  106. 		{"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"LR", 5}, {"RL", 6},
  107. 		{"RR", 7}, {"LLL", 8}, {"LLR", 9}, {"LRL", 10}, {"LRR", 11},
  108. 		{"RLL", 12}, {"RLR", 13}, {"RRL", 14}, {"RRR", 15}
  109. 	};
  110.  
  111. 	for (auto pair: keys)
  112. 		insert(root, pair.first, pair.second);
  113.  
  114. 	printNodes(root);
  115.  
  116. 	return 0;
  117. }
  118.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 7 5 6 8 15 9 14 10 13 11 12
https://ideone.com/cKHzi2
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!