Finding parents in a general tree

I'm making a general tree structure (unlimited number of children), and in some of my functions, I need to determine if a node has a parent. The problem is the nodes don't link back to their parents. Given this, what would be a good method of finding a node's parent?

When I picture the tree structure, I don't see any node not having a parent unless it is the root node, so to check if a node has a parent or not, would all I have to do is compare the node in question to the root node? Is it that simple?

Well, this is just a guess, so take it for what it's worth.

Assuming that you got to any given node by searching down the tree to get there, you can always pass the a pointer to the current node as a parent parameter to your search call. On the initial call, you would pass NULL. So you can always test for the root by checking for NULL. That way you will have the parent pointer during search operations, but you don't have to permenantly store it in the data structure.

Hopefully this helps?

Yes, that is good idea, but looking at my task at hand, I don't think I need to actually refer to the parent node, just see if it has a parent. In which case all nodes in a tree have to have a parent (except the root node), right?

>Is it that simple?
If a non-root node has no parent then you're dealing with a free tree, which is likely a graph. If it's not a graph then it's likely to be a forest. If you want to be truly general then no, it's not that simple. If you just want a tree with potentially more than two children then yes, it is that simple:

Code:

---

bool has_parent ( node *root, node *item )
{
  return root == item;
}

---

Yes, if its possible to compare it to the root then all you need to do is say if its not the root then it has a parent.

[edit] beaten by Prelude ;) [/edit]