Question

C++ How can I print out the subtrees in my self-balancing tree? What I would like to do is have it display something like " ROOT = X, LEFT PARENT = X, X,X, RIGHT PARENT = X,X,X.

Here is my code:

#include <iostream>
using namespace std;

class TreeNode
{
public:
   int data;
   TreeNode* left;
   TreeNode* right;
};

TreeNode* newNode(int data);

/* A function that constructs Balanced
Binary Search Tree from a sorted array */
TreeNode* convertToBTS(int arr[],
   int start, int end)
{
  
   if (start > end)
       return NULL;

   //make the middle number the root
   int mid = (start + end) / 2;
   TreeNode *root = newNode(arr[mid]);

  
   root->left = convertToBTS(arr, start,
       mid - 1);

  
   root->right = convertToBTS(arr, mid + 1, end);

   return root;
}

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
TreeNode* newNode(int data)
{
   TreeNode* node = new TreeNode();
   node->data = data;
   node->left = NULL;
   node->right = NULL;

   return node;
}

//The array will be sorted in PreOrder
void preOrder(TreeNode* node)
{
   if (node == NULL)
       return;
   cout << node->data << " ";
   preOrder(node->left);
   preOrder(node->right);
}

int main()
{
  
   const int SIZE = 7;
   int arr[SIZE];
   int count = 7, num = 0;

   cout << "We will construct a Self-Balancing Tree!\n Enter 6 numbers for the nodes." << endl;

   for (int i = 0; i < SIZE; i++)
   {
       cout << "Enter " << count << " more items!" << endl;      
       cin >> arr[i];
       count--;
   }

   int n = sizeof(arr) / sizeof(arr[0]);

   /* Convert List to BST */
   TreeNode *root = convertToBTS(arr, 0, n - 1);
   cout << "The tree will be displayed in PreOrder!" << endl
       << "First number will be the ROOT. Then LEFT SUBTREE, and RIGHT SUBTREE." << endl;
   preOrder(root);

   return 0;
}

Answer 1

Store the preorder traversal in an array called result and print that in the main function.

#include <iostream>

using namespace std;

class TreeNode

{

public:

int data;

TreeNode* left;

TreeNode* right;

};

TreeNode* newNode(int data);

/* A function that constructs Balanced

Binary Search Tree from a sorted array */

TreeNode* convertToBTS(int arr[],

int start, int end)

{

if (start > end)

return NULL;

//make the middle number the root

int mid = (start + end) / 2;

TreeNode *root = newNode(arr[mid]);

root->left = convertToBTS(arr, start,

mid - 1);

root->right = convertToBTS(arr, mid + 1, end);

return root;

}

/* Helper function that allocates a new node

with the given data and NULL left and right

pointers. */

TreeNode* newNode(int data)

{

TreeNode* node = new TreeNode();

node->data = data;

node->left = NULL;

node->right = NULL;

return node;

}

//The array will be sorted in PreOrder

int result[7];

int index = 0;

void preOrder(TreeNode* node) {

  if (node == NULL)

    return;

result[index++] = node->data;

  preOrder(node->left);

  preOrder(node->right);

}

int main()

{

const int SIZE = 7;

int arr[SIZE];

int count = 7, num = 0;

cout << "We will construct a Self-Balancing Tree!\n Enter 6 numbers for the nodes." << endl;

for (int i = 0; i < SIZE; i++)

{

cout << "Enter " << count << " more items!" << endl;

cin >> arr[i];

count--;

}

int n = sizeof(arr) / sizeof(arr[0]);

/* Convert List to BST */

TreeNode *root = convertToBTS(arr, 0, n - 1);

cout << "The tree will be displayed in PreOrder!" << endl

<< "First number will be the ROOT. Then LEFT SUBTREE, and RIGHT SUBTREE." << endl;

preOrder(root);

cout<<endl;

cout <<"root " << root->data <<endl;

cout <<"left parent " << result[1]<<","<<result[2]<<","<<result[3] <<endl;

cout <<"right parent " << result[4]<<","<<result[5]<<","<<result[6] <<endl;

return 0;

}