Finding the ancestors of a node in a binary tree with only the value of a node

Question

I am trying to finish a method which takes in a value, I have to RECURSIVELY find the the ancestors of a node with a matching value in a binary tree, so far I'm running into a little trouble with the recursive part, here's the class im working with:

#ifndef TREETYPE_H
#define TREETYPE_H
#include <string>
#include <fstream>
#include "QueType.h"
using namespace std;

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template<class ItemType>
struct TreeNode;

template <class ItemType>
class TreeType
{
public:
  TreeType();                     // constructor
 ~TreeType();                    // destructor
  TreeType(const TreeType<ItemType>& originalTree);
  void operator=(const TreeType<ItemType>& originalTree);
  // copy constructor
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  int GetLength() const; 
  ItemType GetItem(ItemType item, bool& found);
  void PutItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetTree(OrderType order); 
  ItemType GetNextItem(OrderType order, bool& finished);
  void Print(ofstream& outFile) const;
  string Ancestors(ItemType item) const;
  string AncestorsNext(TreeNode<ItemType>* node, ItemType item) const;
private:
  TreeNode<ItemType>* root;
  QueType<ItemType> preQue;
  QueType<ItemType> inQue;
  QueType<ItemType> postQue;
};

template <class ItemType>
struct TreeNode
{
  ItemType info;
  TreeNode* left;
  TreeNode* right;
};

And here's what I have so far with my ancestors method:

// This recursive function will return the ancestors of item in reverse order.
template <class ItemType>
string TreeType<ItemType>::Ancestors(ItemType item) const{
    string out="";
    TreeNode<ItemType>* temp=root;
    if(root==nullptr || root->info==item){
        return "Value has no ancestors";
    }
    else{

        if(temp->info>item){
            out+=temp->info;
            temp=temp->left;
            TreeType<ItemType>::Ancestors(temp->info);
        }
        if(temp->info<item){
            out+=temp->info;
            temp=temp->right;
            TreeType<ItemType>::Ancestors(temp->info);
        }
    }

    return out;

}

Im stuck on how I can use recursion to check the next value in the tree with my temp variable if it just gets set to root everytime. If there's another way im all ears!

Answer 1

I m stuck on how I can use recursion to check the next value in the tree with my temp variable if it just gets set to root everytime.

---

This is a common mistake with a simple solution. (But maybe not if you can not add a method)

Essentially, you are trying to do too-many-things in one function.

The simple solution is to split your current function into 2 functions,

a) one that handles the initialization of where to start searching, which is not recursive,

b) and another that performs the recursion.

I hope the following provides enough hint for you (as I am not practiced with templates)

template <class ItemType>
string TreeType<ItemType>::Ancestors(ItemType item) const
{
    string out = AncestorsR(item, root)  // invoke recursive funct
    return out;
}

template <class ItemType>
string TreeType<ItemType>::AncestorsR(ItemType item,
                           TreeNode<ItemType>* temp) const
{
    string out="";

    if(temp==nullptr || temp->info==item)
    {
        return "Value has no ancestors";
    }
    else
    {
        if(temp->info>item)
        {
            out+=temp->info;
            temp=temp->left;
            TreeType<ItemType>::Ancestors(temp->info);
        }
        if(temp->info<item)
        {
            out+=temp->info;
            temp=temp->right;
            TreeType<ItemType>::Ancestors(temp->info);
        }
    }
    return out;
}