How do I sort linked list using in-order traversal?

[nexteon]

I am trying to make my inOrder function work for my test file. My function is supposed to order a string of data in a binary search tree. I expected my code to do just that but so far an only got the code to print out the root. I tried changing my function parameters to match the string of data but I'm it gives me errors. I know the algorithm is simple but I just can't figure out what parts of code go where. The code I am showing is my only attempt that runs. The code below is my Test File

#include <string>
#include "bst.h"
using namespace std;

string data[] = { "able", "baker", "charlie", "dog", "easy", "fox", "george" };
    int size = 7;
    binary_search_tree<string> bst1;
    for (int i = 0; i < size; ++i) {
        bst1.insert(data[i]);
        cout << bst1 << endl;
    }
    cout << "balanced? " << bst1.is_balanced() << endl << endl;


        bst1.inOrder(bst1.get_root());

This is my Template

#include "bst.h"
#include <string>
#include <iostream>
/**
    * Add the item to this binary search tree as long as it
    * is not already present.
    * Return false if item is already  in the tree.
    * Return true if item is actually added to the tree.
    */
template <class T>
bool binary_search_tree<T>::insert(const T &item) {
    root = new binary_tree_node<T>(item);

    if(root == NULL)
    {
        insert(item);
    }

    if(root->data() == item)
    {
        return false;
    }else
    {
        return true; 
    }
}

/**
    * return the depth of the tree if the tree is balanced.
    * Return -2 if not.
    */
template <class T>
int  binary_search_tree<T>::is_balanced() {
    return check_balanced(root);
}

template <class T>
std::ostream &operator<<(std::ostream &out, const binary_tree_node<T> *root) {
    if(root != NULL) {
        out << "[";
        out << root->left() << " ";
        out << root->data();
        out << " " << root->right();
        out << "]";
    }
    return out;
}



template <class T>
std::ostream &operator<<(std::ostream &out, const binary_search_tree<T> &tree) {
    out << tree.root;
    return out;
}


template<class T>
void binary_search_tree<T>::inOrder(binary_tree_node<T>* ptr)
{

if(ptr != NULL)

{

    inOrder(ptr->left());

    std::cout << ptr->data();

    //if(ptr->left() != NULL && ptr->right() != NULL)

    std::cout << " " ;

    inOrder(ptr->right());

}

This is my HEADER

#ifndef BST_H
#define BST_H

#include "bintree.h"
#include <iostream>
template <class T>
class binary_search_tree {

public:
    binary_search_tree() {
        root = NULL;
    }

    /**
     * Add the item to this binary search tree as long as it
     * is not already present.
     * Return false if item is already  in the tree.
     * Return true if item is actually added to the tree.
     */
    bool insert(const T& item);



    ~binary_search_tree();


    /**
     * return the depth of the tree if the tree is balanced.
     * Return -2 if not.
     */
    int is_balanced();

    template <class S>
    friend std::ostream& operator<<(std::ostream& out, const binary_search_tree<S>& tree);

    binary_tree_node<T>* get_root() { return root; }

    void inOrder(binary_tree_node<T>*);
    //void inOrder(const T& item);
    //void inOrder();

private:
    binary_tree_node<T>* root;
};


template <class T>
std::ostream& operator<<(std::ostream& out, const binary_tree_node<T>* root);


#include "bst.template"


#endif // BST_H 

[dutch]

Your insert function is nuts.
Take another shot at it.

[nexteon]

It actually works when I tried it with my test file. Do you see it interfering with the inOrder function somehow?

[dutch]

This is your insert function (rewritten for clarity).
It is insane.
Think about it.
How could it possibly work?

template <class T>
bool binary_search_tree<T>::insert(const T &item)
{
    root = new binary_tree_node<T>(item);
    if (!root) insert(item);
    return root->data() != item;
}

[nexteon]

I was just following the conditions that were given to me. Return false if the item is already in the tree. I put in the code you've written and it works fine as well.

[mbozzi]

Just because some code compiles and runs doesn't mean that it produces the right answer.

The current implementation is patently wrong. It doesn't even traverse the tree to figure out where to place the item.

[nexteon]

Okay, I was looking at it. I'm still confused, seeing that I was following the algorithm
Check if the root is null, Allocate a node and set the root to item;
If item == root ->data , then return false
else If the item < root, call insert(item)
else If the item > root, call insert( item)
and conditions
/**
* Add the item to this binary search tree as long as it
* is not already present.
* Return false if item is already in the tree.
* Return true if item is actually added to the tree.
*/
. I thought the recursion was traversing the tree from each node.

[dutch]

I put in the code you've written and it works fine as well.

In what sense does it "work fine"?
Post the whole program for that so I can run it.

[nexteon]

https://stackoverflow.com/questions/61047271/how-do-i-get-my-inorder-function-to-work-for-a-binary-search-tree-of-strings?noredirect=1#comment108000908_61047271

Here is a link to the full access to my code. It's too big for the forum.

[mbozzi]

Hopefully this example will help:

#include <iostream>
#include <string>

class bst
{
  struct node
  {
    node* left_  = nullptr;
    node* right_ = nullptr;
    
    explicit node(std::string const& data, node* left = nullptr, node* right = nullptr)
      : left_(left), right_(right), data_(data)
    {}

    std::string data_;

    bool insert(std::string const& data)
    {
      return (data  < data_)? insert_subtree(data, left_)
           : (data_ < data )? insert_subtree(data, right_)
           : false;
    }
  } *root_ = nullptr;
  
  friend bool insert_subtree(std::string const& data, node*& child)
  {  
    return child? child->insert(data): bool{child = new node(data)};
  }
  
  void destroy(node* n)
  { 
    if (n) 
    { 
      destroy(n->left_);  
      destroy(n->right_);
    }
    
    delete n;
  }
  
  void print_in_order_impl(node* const n) const 
  {
    if (n) 
    {
      print_in_order_impl(n->left_);
      std::cout << n->data_;
      print_in_order_impl(n->right_);
    }
  }
        

public:
  bool insert(std::string const& data)
  { 
    return insert_subtree(data, root_); 
  }
  
  void print_in_order() const
  {
    print_in_order_impl(root_);   
  }
  
  bst() = default;
  
  bst(bst const&) = delete;
  bst& operator=(bst) = delete;
  ~bst() { destroy(root_); }
};

int main()
{
  bst tree;
  
  for (auto elt : { "D", "G", "A", "H", "F", "J", "E", "C", "I", "B" })
    tree.insert(elt);
    
  tree.print_in_order();
}

[nexteon]

That example actually helps a lot. Thank you mbozzi.