Binary Tree operator overloading and recursion

Answer 1

Generally the idea in these cases is to have a data structure which is a tree consisting of trees and leaf nodes. Something like

struct TreeType
{
    std::vector<TreeType> subtrees;
    std::vector<LeafNodes> leafs;
}

This allows one to define a == operator along the lines of

bool TreeType::operator==(const TreeType& rhs) const
{
    if each subtree == subtree && each leaf == leaf
    then true
    else false
}

Here the subtree comparison will call the == operator recursively on the children trees.

EDIT: It would be handy if you provided the exact organization of your TreeType data structure to allow for a better/specific answer.

Answer 2

It would probably be easiest to add equality operator to the node class.

struct node
{
    int info;
    node * left;
    node * right;

    friend bool operator==(node const & lhs, node const & rhs)
    {
        return lhs.info == rhs.info
            && ((lhs.left == 0 && rhs.left == 0)
                || (lhs.left != 0 && rhs.left != 0 && *lhs.left == *rhs.left))
            && ((lhs.right == 0 && rhs.right == 0)
                || (lhs.right != 0 && rhs.right != 0 && *lhs.right == *rhs.right));
    }
};

Then you can simply compare root nodes from TreeType::operator==.

bool TreeType::operator==(const TreeType& otherTree) const
{
    return (root == 0 && otherTree.root == 0)
        || (root != 0 && otherTree.root != 0 && *root == *otherTree.root);
}

Answer 3

Given this class:

class TreeNode
{
  TreeNode* left;
  TreeNode* right;
  int value;

  bool operator==(const TreeNode& node);
};

I would write the == operator like this:

bool TreeNode::operator==(const TreeNode& node)
{
  // Are we comparing the node to itself ?
  if (&node == this)
    return true;

  // We have a left node
  if (left != NULL)
  {
     // Does node have a left node too ?
     if (value.left != NULL)
     {
       // Are they different ?
       if (!(*left == *value.left))
         return false;
     } else
       // Node has no left node
       return false;
  } else
  {
    // We don't have a left node, does node have one ?
    if (value.left != NULL)
      return false;
  }

  // We have a right node
  if (right != NULL)
  {
     // Does node have a right node too ?
     if (value.right != NULL)
     {
       // Are they different ?
       if (!(*right == *value.right))
         return false;
     } else
       // Node has no right node
       return false;
  } else
  {
    // We don't have a right node, does node have one ?
    if (value.right != NULL)
      return false;
  }

  // Return true only if we have the same value.
  return (value == node.value);
}

Of course the recursion "end-conditions" can be switched for the algorithm to be optimized (checking the values first might be more efficient).

This is left to you as an exercise :D