In order traversal for binary search tree without node pointer as parameter

Question

I have to code up a function for a lab in a binary search tree for in order traversal. My problem is I've been given an interface that I have to follow and in it the only parameter I can pass to the traversal function is another function of void return type:

void BinarySearchTree<ItemType, KeyType>::inorderTraverse(void visit(ItemType&)) const

The visit function is basically a function that I would define for a specific use case for the tree, like say I want to print out the tree in ascending order in which case the function I would pass to the inorderTraverse function would be a print function. I can't figure out how to traverse the entire tree without having a node pointer as a parameter. I'm not asking for the entire code, just advice that can point me in the right direction! Here's the BinarySearchTree.h:

template<typename ItemType, typename KeyType>
class BinarySearchTree
{
private:
   BinaryNode<ItemType>* rootPtr;

   // Recursively deletes all nodes from the tree.
   void destroyTree(BinaryNode<ItemType>* subTreePtr);

   // Recursively finds where the given node should be placed and
   // inserts it in a leaf at that point.
   BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
                                   BinaryNode<ItemType>* newNode);

   // Returns a pointer to the node containing the given value,
   // or nullptr if not found.
   BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
                              const KeyType& target) const;

public:
   //------------------------------------------------------------
   // Constructor and Destructor Section.
   //------------------------------------------------------------
   BinarySearchTree();
   virtual ~BinarySearchTree();

   //------------------------------------------------------------
   // Public Methods Section.
   //------------------------------------------------------------
   bool add(const ItemType& newEntry);
   ItemType getEntry(const KeyType& aKey) const throw(NotFoundException);
   bool contains(const KeyType& aKey) const;

   //------------------------------------------------------------
   // Public Traversals Section.
   //------------------------------------------------------------
   void inorderTraverse(void visit(ItemType&)) const;
}; // end BinarySearchTree

#include "BinarySearchTree.cpp"

#endif

you might find this helpful: stackoverflow.com/questions/18413705/… — Falla Coulibaly
– Falla Coulibaly, Commented Nov 4, 2016 at 5:30
No, that's exactly my problem, I can't pass a node pointer to my function and that's why I can't figure out how to traverse recursively — juzerzarif
– juzerzarif, Commented Nov 4, 2016 at 5:33
Not necessarily, it's just the post you referred me to was using recursion and I don't really know of any other way you could traverse a binary tree. Sorry, I'm not very experienced with this stuff! — juzerzarif
– juzerzarif, Commented Nov 4, 2016 at 5:53
void BinarySearchTree<ItemType, KeyType>::inorderTraverse(...) const is a method of the BinarySearchTree -as such, you do have access to the root node of the tree inside the mehod. Your visitor won'y receive the node itself, but the visitor does not need to traverse the tree: it is the inorderTraverse that should do it. — Adrian Colomitchi
– Adrian Colomitchi, Commented Nov 4, 2016 at 6:03

Community · Accepted Answer · 2017-05-23 12:33:18Z

I'm assuming the BinaryNode has the methods

const BinaryNode* getLeft() const;
const BinaryNode* getRight() const;
const ItemType& getValue() const;

[Edited due to: "got told that we couldn't add anything extra to the class"]

You see, that method is static - it means it doesn't rely on any knowledge about the particular instant of your tree.

Because of this, it can be placed anywhere.

For example, just write it as a static function outside the class, inside your "BinarySearchTree.cpp" file.

Another solution: implement it inside the inorderTraverse method, as a lambda function like in:

  // as a method of this class, you **do** have access to the root node
  void inorderTraverse(void visit(const ItemType&)) const {
    // this is a lambda function
    auto inOrderRecurse=(
      const BinaryNode<ItemType>* node, 
      void visit(const ItemType&)
    ) {
         if(node) {
           auto n=node->getLeft();
           if(n) {
              this->inOrderRecurse(n, visit);
           }
           visit(node->getValue());
           n=node->getRight();
           if(n) {
             this->inOrderRecurse(n, visit);
           }
        }
      }
    ;
    inOrderRecurse(this->rootPtr);
  }

Yet another solution: if you aren't allowed to use lambdas, you can still declare a class/structure inside you method. So, let's declare/use one in the very inorderTraverse method.

  // as a method of this class, you **do** have access to the root node
  void inorderTraverse(void visit(const ItemType&)) const {
    struct recurser {
      static void inOrderRecurse(
        const BinaryNode<ItemType>* node, 
        void visit(const ItemType&)
      ) {
       // etc...
      }
    };
    recurser::inOrderRecurse(this->rootPtr);
  }

[original answer]

As such, the inorderTraverse can be implemented as:

private:
  // "All problems in computer science can be solved by another level of indirection, 
  // except of course for the problem of too many indirections."
  // In the context, **this method** is another level of indirection
  static void inOrderRecurse(
      const BinaryNode<ItemType>* node, 
      void visit(const ItemType&)
  ) const {
   if(node) {
     auto n=node->getLeft();
     if(n) {
       this->inOrderRecurse(n, visit);
     }
     visit(node->getValue());
     n=node->getRight();
     if(n) {
       this->inOrderRecurse(n, visit);
     }
  }
public:

  // as a method of this class, you **do** have access to the root node
  void inorderTraverse(void visit(const ItemType&)) const {
    // note this `const` here  ---^ needed because of ^^^^ this one
    inOrderRecurse(this->rootPtr);
  }

I was told I can't add any private helper functions. Because that's what I was going to do originally but then our class got told that we couldn't add anything extra to the class, just define the methods that need definition.
@pyro97 Updated my answer with workarounds the requirement "no extra methods to the BinaryTree class"

Collectives™ on Stack Overflow

In order traversal for binary search tree without node pointer as parameter

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related