fork download
copy 
  1. #include <iostream>
  2. #include <array>
  3. using namespace std;
  4.  
  5. struct Node {
  6. 	int data;
  7. 	Node *left;
  8. 	Node *right;
  9.  
  10. 	Node(int val) {
  11. 		this->data = val;
  12. 		this->left  = NULL;
  13. 		this->right = NULL;
  14. 	}
  15. };
  16.  
  17. /* creates binary search tree with minimal height from sorted array */
  18. Node *makeBSTfromArray(int *a, int min, int max) {
  19. 	if (min > max) 
  20. 	    return NULL;
  21.  
  22. 	int mid = (min + max) / 2;
  23. 	Node *root = new Node(a[mid]);
  24. 	root->left  = makeBSTfromArray(a, min, mid-1);
  25. 	root->right = makeBSTfromArray(a, mid+1, max);
  26.  
  27. 	return root;
  28. }
  29.  
  30. /* compute the "height" of a tree -- distance from root node to farthest leaf */
  31. int height(Node *node)
  32. {
  33.     if (node == NULL) return 0;
  34.  
  35.     int lheight = height(node->left);
  36.     int rheight = height(node->right);
  37.  
  38.     return (lheight > rheight) ? lheight+1 : rheight+1;
  39. }
  40.  
  41. /* util function -- prints all nodes at given level of tree */
  42. void printTreeAtLevel(Node *node, int level) {
  43. 	if (node == NULL) return;
  44.  
  45. 	if (level == 1)
  46. 	    printf("%d ", node->data);
  47. 	else {
  48. 		printTreeAtLevel(node->left, level-1);
  49. 		printTreeAtLevel(node->right, level-1);
  50. 	}
  51. }
  52.  
  53. /* print out level order traversal of tree */
  54. void printTreeLevelOrder(Node *node) {
  55. 	int h = height(node);
  56.  
  57. 	for (int i = 1; i < h; i++) {;
  58. 		printf("%d: ", i);
  59. 		printTreeAtLevel(node, i);
  60. 		printf("\n");
  61. 	}
  62. }
  63.  
  64.  
  65.  
  66. int main() {
  67.  
  68.     int input[] = {3,4,5,6,7,8,9,10,12,13};
  69.       //output = {7,4,3,5,6,10,8,9,12,13}
  70.  
  71.     Node *root = makeBSTfromArray(input, 0, 10-1);
  72.     printTreeLevelOrder(root);
  73.  
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1: 7 
2: 4 10 
3: 3 5 8 12
https://ideone.com/TNwQB5
language:
C++ (gcc 8.3)
created:
7 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!