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 key;
  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->key = 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. // Function to print all nodes of a given binary tree in specific
  48. // order from top to bottom
  49. void printNodes(Node* root)
  50. {
  51.     // return is tree is empty
  52. 	if (root == nullptr)
  53. 		return;
  54.  
  55.     // print root node
  56. 	cout << root->key << " ";
  57.  
  58.     // create an two empty queues and enqueue root's left and
  59.     // right child respectively
  60. 	queue<Node *> Q1, Q2;
  61. 	if(root->left)
  62. 		Q1.push(root->left);
  63. 	Q2.push(root->right);
  64.  
  65.     // run till queue is not empty
  66. 	while (!Q1.empty())
  67. 	{
  68. 		// calculate number of nodes in current level
  69. 		int n = Q1.size();
  70.  
  71. 		// process every node of current level
  72. 		while (n--)
  73. 		{
  74. 		    // pop front node from first queue and print it
  75. 			Node* x = Q1.front();
  76. 			Q1.pop();
  77.  
  78. 			cout << x->key << " ";
  79.  
  80. 			// push left and right child of x to first queue
  81. 			if (x->left)
  82. 				Q1.push(x->left);
  83.  
  84. 			if (x->right)
  85. 				Q1.push(x->right);
  86.  
  87.  
  88. 		    // pop front node from second queue and print it
  89. 			Node* y = Q2.front();
  90.             Q2.pop();
  91.  
  92. 			cout << y->key << " ";
  93.  
  94. 			// push right and left child of y to second queue
  95. 			if (y->right)
  96. 				Q2.push(y->right);
  97.  
  98. 			if (y->left)
  99. 				Q2.push(y->left);
  100. 		}
  101. 	}
  102. }
  103.  
  104. // main function
  105. int main()
  106. {
  107. 	Node* root = nullptr;
  108. 	vector<pair<string, int> > keys =
  109. 	{
  110. 		{"", 1}, {"R", 3}, {"RL", 6},
  111. 		{"RR", 7}
  112. 	};
  113.  
  114. 	for (auto pair: keys)
  115. 		insert(root, pair.first, pair.second);
  116.  
  117. 	printNodes(root);
  118.  
  119. 	return 0;
  120. }
  121.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/AMWrer
Print all nodes of a given binary tree in specific order from top to bottom
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!