Binary Search Tree

[salem alqahtani]

Hi,

I am building a binary search tree project and I am interested to fill up the vector by taking the order value from the binary tree(Takes a vector reference, and fills the vector with the tree values in sorted order).

The project involves many things and I tested many parts of it but I am not sure why the following pieces do not make any sense for me even though I wrote it but I still have a confusion. Basically, I want some body to point out any major problem with my code.

  

Here is my try:

BSTree.cpp

void BSTree::sortedArray(vector<int> &list){
  // do something
   list.sortedArrayprivate(root);
}

void BSTree::sortedArrayprivate(Node* ptr){
  // do something
   if(root != NULL)
   {
    if(ptr->left != NULL)
    {
      sortedArrayprivate(ptr->left);
    }
    cout<<ptr->key_value<<endl;
    if(ptr->right != NULL)
    {
      sortedArrayprivate(ptr->right);
    }
   }
   else{
    cout<<"The tree is empty"<<endl;
   }
}
Here is the Header File: BSTree.h

class BSTree
{
    private:
        class Node
        {
                int key_value;
                Node* left;
                Node* right;
        };
        Node* root;
        void sortedArrayprivate(Node* ptr);
    public:
        void sortedArray(std::vector<int> &list);
};

[coder777]

What are you trying to do in sortedArrayprivate(...)? Currently you only print the key_value of the left part.

line 14 should be if(ptr != NULL).

[dhayden]

When coding recursive functions, I always like to write code as

if (base case) {
    do the base case
} else {
    do the recursive case
}

This ensures that you don't forget the base case, which is really easy to do. And for the binary tree, it also simplifies the code. For example, to print a subtree:

void BSTree::printTree(Node* ptr){
   if(ptr == NULL) {
      return;
   } else {
      printTree(ptr->left);
      cout<<ptr->key_value<<endl;
      printTree(ptr->right);
   }
}

To populate the array, you need to pass the array to the private routine. You'll find that you also need to pass the index down too:

void BSTree::sortedArray(vector<int> &vec){
   size_t index=0;
   list.sortedArrayprivate(root, vec, index);
}

void BSTree::sortedArrayprivate(Node* ptr, vector<int> &vec, size_t &index){
   if(ptr == NULL) {
      return;
   } else {
      sortedArrayprivate(ptr->left, vec, index);
      vec[index++] = ptr->key_value;
      sortedArrayprivate(ptr->right, vec, index);
   }
}