Member Avatar for techie929

// error: expected constructor, destructor, or type conversion before '*' token
*** Error code 1
make: Fatal error: Command failed for target `bst.o'

class BinarySearchTree
{
        private:
        int count;
		int n;
        struct tree_node
			{
			   tree_node* left;
			   tree_node* right;
			   char data[1000];
			   
			};
        tree_node* root;

        public:
			BinarySearchTree()
			{
			   root = NULL;
				count = 0;
				 n=1;
			 
			}
        
		bool isEmpty() const { return root==NULL; }
		void print_preorder();
		void print_format(tree_node*,int,int[100],char) const;
		void preorder(tree_node*,int,int[100],char) const;
		void insert(char*);
		void remove(char*);
		bool search(char*);
		tree_node* inorderSuccessor(tree_node*); /* Finds the inorder successor of a node */
		int num_nodes();
		//int countNodes(tree_node *&root);
  
};



tree_node* BinarySearchTree::inorderSuccessor(tree_node* p )
	{
  
   if(!p) return NULL;
   p=p->right;
    if (!p) return NULL;
 
    while (p->left) {
        p= p->left;
    }
    return p;
}
  • 3 Contributors
  • 3 Replies
  • 126 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by mitrmkar

Dani AI

Generated

The compile error comes from C++ name lookup: tree_node is declared inside BinarySearchTree, so when you define a member function outside the class you must refer to that nested type with the class scope. pointed this out; the signature the compiler sees (an unqualified tree_node* outside the class body) is what triggers the "expected constructor, destructor, or type conversion before '*' token" message reported by .

Use a fully qualified signature for the out-of-class definition so both the return type and the parameter type are resolved:

BinarySearchTree::tree_node* BinarySearchTree::inorderSuccessor(BinarySearchTree::tree_node* p) {
    // implementation
}

Other fixes: define inorderSuccessor inside the class (no qualification needed), move tree_node out to namespace/global scope, or add a public type alias inside the class and use it consistently. Note: if tree_node is private, type aliases or uses outside the class won't be accessible — keep the declaration and the out-of-class definition in the same translation unit (include the header) and respect access levels.

A correctness note beyond the compilation fix: the code posted only finds the leftmost node of p->right. That is correct when p has a right subtree. For the general inorder-successor problem you also must handle the case when p has no right child. Two common approaches:

  • Give nodes a parent pointer and walk up until you find an ancestor where you came from its left child.
  • If you do not have parent pointers, traverse from root, tracking the best successor candidate: when you go left, update candidate to the current node; when you go right, do not. If you find p, return the candidate (or the leftmost node of p->right if it exists). Replace comparisons with strcmp (or better, use std::string) to compare char[] data safely. Also consider using std::string and modern RAII (smart pointers) instead of raw char[] and raw pointers.

Recommended Answers

All 3 Replies

Member Avatar for Nick Evan

Which line?

Member Avatar for techie929

Line 40

Member Avatar for mitrmkar

Line 40

Since tree_node is nested inside the BinarySearchTree class, you need to apply the scope resolution operator ..

[B]BinarySearchTree[/B]::tree_node * BinarySearchTree::inorderSuccessor(tree_node* p ){}

or make the declaration of tree_node public and use a typedef ..

typedef BinarySearchTree::tree_node treeNode;
treeNode * BinarySearchTree::inorderSuccessor2(tree_node* p ){}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.