Fastest way to search for a node in a tree in C++

Question

#ifndef __TREE_H
#define __TREE_H
#include <cstdlib>
#include<string>

// structure of a tree node

struct TreeNode{
        string str;
        TreeNode *parent;
        TreeNode *leftChild;
        TreeNode *nextSibling;

        TreeNode(string str1){
                this->str = str1;
                this->parent = NULL;
                this->leftChild = NULL;
                this->nextSibling = NULL;
        }

};

class Tree{

        TreeNode* root;
        int size;

public:

        Tree();         //constructor

        void insert(string str1);       //insert a node

        string locate(string str1);     //locate a node

        TreeNode *ancestor(string str1, string str2);   //get lowest common ancestor
};


#endif

this is a class of a generic tree (not a binary tree). What will be the fastest way to implement the locate function? should i go through all the child first and then the siblings or what?

Answer 1

If the tree is unordered there is no algorithm other than brute force testing of all nodes and break out when the element is found (if found). When dealing with trees, recursion is usually the simplest approach. The pseudo algorithm could be something like:

find(current_node,value):

if current_node.value == value
   return found
else 
   if find(current_node.left,value) == found
      return found
   else if find(current_node.right,value) == found
      return found
   else
      return not_found

Of course, when really implementing this you will need to test for null pointers, and so on. Without any other constraints on the tree, the asymptotic complexity cannot be reduced. You might be able to come with a non-recursive approach or a tail-recursion algorithm (based on the above) that might improve the constant factors, but don't expect a huge improvement there.