Insert/find issues in Binary Tree

Question

UPDATE: This issue only appears when I use the binary tree for strings. If I feel it with ints, everything works fine!

A few months ago I wrote a Binary Tree implementation in C++. Everything seemed to work okay (insert, remove, traversals, find...) and I passed my exams :) But now when I write a new class based on this binary tree class, the find method seems to be buggy, but I can't find the reason.

Here is the issue: find returns a pointer to a node, but for some reason I can access its member variables only when this node is the root. I can't quite understand why. Something to do with poiters? Or is there something wrong in my insert function? Can someone help me, because I feel a bit lost :)

Here is my Binary Tree interface:

template <class N>
class Node {
public:
  N data;
  Node* left;
  Node* right;
  Node* parent;
};

template <class B>
class BinaryTree {
protected:
  Node<B>* m_root;
  unsigned int m_height;  // longest path in tree
  unsigned int m_size;    // total number of nodes

  // methods that support public methods of below
  void __insert(Node<B>* element, B value);
  void __inorder(Node<B>* element);
  void __preorder(Node<B>* element);
  void __postorder(Node<B>* element);
  void __remove(Node<B>* element, B value);
  void __update_parent(Node<B> *element);
  void __destroy_tree(Node<B>* element);
  int __get_height(Node<B>* element);
  Node<B>* __find(Node<B>* element, B value);
  Node<B>* __find_minimal(Node<B> *element);

public:
  BinaryTree(); // Default constructor
  ~BinaryTree(); // Default deconstructor
  void insert(B value);
  void inorder();
  void preorder();
  void postorder();
  void remove(B value);
  int get_size();
  int get_height();
  bool is_empty();
  bool find(B value);
  bool check_find(B value);
};

Insert:

template <class B>
void BinaryTree<B>::insert(B value) {      // Creates a new node in the tree with value
  if(m_root == NULL) {
    m_root = new Node<B>;   // creating the root if it's empty
    m_root->data = value;
    m_root->left = NULL;
    m_root->right = NULL;
    m_root->parent = NULL;
  }
  else {
    Node<B>* element = m_root;
    __insert(element, value);
  }
}

template <class B>
void BinaryTree<B>::__insert(Node<B>* element, B value) {
  if(value < element->data) {
    if(element->left != NULL)
      __insert(element->left, value);
    else {
      element = element->left;
      element = new Node<B>;
      element->data = value;
      element->left = NULL;
      element->right = NULL;
      element->parent = element;
      m_size++;
    }
  }
  else if(value >= element->data) {
    if(element->right != NULL)
      __insert(element->right, value);
    else {
        element = element->right;
        element = new Node<B>;
        element->data = value;
        element->left = NULL;
        element->right = NULL;
        element->parent = element;
        m_size++;
    }
  }
}

Find:

template <class B>
Node<B>* BinaryTree<B>::__find(Node<B>* element, B value) {
  if(element != NULL) {
    if(value == element->data)
      return element;
    else if(value < element->data)
      __find(element->left, value);
    else if(value > element->data)
      __find(element->right, value);
  }
  else
    return NULL;
}

Finally, a function that tests find. Even if the values match, it returns only True when the found node is m_root. Why?

template <class B>
bool BinaryTree<B>::check_find(B value) {
  Node<B>* node = __find(m_root, value);
  if(node != NULL && node->data == value)
    return true;
  return false;
}

Why?

More links: Full code of my Binary Tree implementation: https://github.com/vgratian/CS-121-Data-Structures/tree/master/graphs Program where I use this Binary Tree: https://github.com/vgratian/rate-ur-prof

Unrelated to your question, but don't use symbols with double leading underscores as those are reserved for the "implementation" (compiler and standard library). See [this question and its answers for more information](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier). — Some programmer dude, Jan 11 '17 at 14:58
As for your problem, take a look at your `__find` function again, and think about if all paths return a value. A compiler should have shouted warnings about it to you. — Some programmer dude, Jan 11 '17 at 15:00

score 0 · Answer 1 · answered Jan 11 '17 at 15:54

0

in your insert function, you don't actually insert the element into the tree. you create a new node, and set it's parent to point to itself. also, you didn't updated the parent left/right pointers to the new node.

take a look in the added comments:

if(element->left != NULL)
  __insert(element->left, value);
else { // meaning element->left == NULL
  element = element->left; // element = NULL
  element = new Node<B>; // element = new node
  element->data = value;
  element->left = NULL;
  element->right = NULL;
  element->parent = element; // element->parent = new node.element parent point to himself

answered Jan 11 '17 at 15:54

sicarii443

51
5

That is not the problem, I think, because otherwise (if I didn't insert the object to the tree) traversal wouldn't work. But it does! – vgratian Jan 11 '17 at 17:59
@vgratian This might be another problem with the code. – moooeeeep Jan 11 '17 at 19:17
I realized now that everything works fine when I use the BT for int, the problem appears only when I feel it with strings... I am really confused now :( – vgratian Jan 11 '17 at 19:39

score 0 · Accepted Answer · answered Jan 11 '17 at 19:54

0

The problem lies with your find implementation:

else if(value < element->data)
  __find(element->left, value);
else if(value > element->data)
  __find(element->right, value);

This only works for types/classes for which the relational operators < and > are defined (in a relevant way). So it will not work whe B is an std::string for example.

For string matching, consider using a Trie.

answered Jan 11 '17 at 19:54

ApprenticeHacker

21,351
27
103
153

You are ***so*** close to the problem. And `std::string` have [relational operators](http://en.cppreference.com/w/cpp/string/basic_string/operator_cmp). – Some programmer dude Jan 12 '17 at 06:57
Many thanks! That seemed to be the problem. It's interesting because relational operators would normally work for strings... Anyway, I solved the problem by adding a new member to my node: unsigned int id and sorting the tree by this variable rather than std::string. This way every works fine. I will need some time to be able to implement a Trie, obviously that would be a much better solution. Thanks again everyone! :) – vgratian Jan 12 '17 at 12:11

Insert/find issues in Binary Tree

2 Answers2