Member Avatar for JackDurden

I want to find the first null child in a tree and return that node of the tree.

Im thinking something like this but it doesnt seem to work the way I want.

node *Find_Empty_Node(node* root)
{
	int index = 0;
	if(root)
	{
		if(root->data == 0)//<--I want this child
				return tree->child[index];

			for(int i = 0;i<root->child.size();i++)
			{
				Find_Empty_Node(root->child[i]);
				index = i;
			}
	}
	return tree;
}

and then back where is called do something like this?

node* curr = root;
curr = Find_Empty_Node(node* root);
  • 4 Contributors
  • 5 Replies
  • 125 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by rcollins

Dani AI

Generated

There are two different things people often mean by "find the first NULL" and it changes the solution: either (A) locate the first child pointer that is actually null (a missing child slot), or (B) locate the first node whose payload is the sentinel value (for example 0). Also decide what "first" means: preorder (depth-first) vs level-order (breadth-first). mentioned preorder; and touched on the recursion-return issue; pointed out returning the wrong pointer (global vs the node you found).

A simple, correct preorder (DFS) pattern is: test the current node, recurse through children, and always capture the recursive result and return it only when non-null. This makes the recursion stop as soon as a match is found.

node* findFirstEmptyValue(node* cur) {
    if (!cur) return nullptr;
    if (cur->value == 0) return cur;        // match sentinel
    for (node* child : cur->children) {
        node* found = findFirstEmptyValue(child);
        if (found) return found;            // propagate match up
    }
    return nullptr;
}

If "first" means level-order (the leftmost node at the shallowest depth with the sentinel), use a queue (BFS). That will find the earliest node by levels:

node* findFirstEmptyLevel(node* root) {
    if (!root) return nullptr;
    std::queue<node*> q;
    q.push(root);
    while (!q.empty()) {
        node* n = q.front(); q.pop();
        if (n->value == 0) return n;
        for (node* child : n->children) if (child) q.push(child);
    }
    return nullptr;
}

If you truly need the first null child pointer in a children array, check each child pointer for nullptr and return the parent plus index (or set the child there). Key pitfalls to avoid: do not return a global root, do not unconditionally return inside the child loop without checking the recursive result, and always return a pointer to the matching node (or parent+index) so the caller can update it. Both DFS and BFS are O(N) worst-case.

Recommended Answers

All 5 Replies

Member Avatar for Sky Diploma 
node *Find_Empty_Node(node* root)
{
	int index = 0;
	if(root)
	{
		if(root->data == 0)//<--I want this child
				return tree->child[index];

			for(int i = 0;i<root->child.size();i++)
			{
                                index = i;
				return Find_Empty_Node(root->child[i]);
			}
	}
	return tree;
}

Shouldnt this be the way to do it?
I mean return the Empty Node as this is a example of a Recursive Function.

Member Avatar for JackDurden

Yeah this works...I meant I want it to stop after it finds the first null child. I cant figure out how to do it.

Member Avatar for VernonDozier 
node *Find_Empty_Node(node* root)
{
	int index = 0;
	if(root)
	{
		if(root->data == 0)//<--I want this child
				return tree->child[index];

			for(int i = 0;i<root->child.size();i++)
			{
                                index = i;
				return Find_Empty_Node(root->child[i]);
			}
	}
	return tree;
}

Shouldnt this be the way to do it?
I mean return the Empty Node as this is a example of a Recursive Function.

Seems to me you need an if-statement in there (around line 12) to check whether Find_Empty_Node has found an empty node. Jack Durden's code goes through the whole loop regardless of whether it finds an empty node. Your code will never go through the whole loop. You want to either go through the whole loop or not depending on whether an empty node is found.

for(int i = 0;i<root->child.size();i++)
{
    node* nodeFound = Find_Empty_Node(root->child[i]);
    if (nodeFound != NULL && nodeFound->data == 0)
        return nodeFound;
}

I think this function may have some other problems. In particular, I'm not sure it will ever return below the first level of children due to these lines:

return tree->child[index];

and

return tree;

I assume tree is the overall root node for the entire tree.

commented: I FORGOT ABOUT THAT :) +3
Member Avatar for JackDurden

Yeah thats what im trying to do, get it to go through all the levels of the tree until it finds the first null child. I thought like a preorder traversal implementation would do the trick...but its not working.

Member Avatar for rcollins

I want to find the first null child in a tree and return that node of the tree.

Im thinking something like this but it doesnt seem to work the way I want.

node *Find_Empty_Node(node* root)
{
	int index = 0;
	if(root)
	{
		if(root->data == 0)//<--I want this child
				return tree->child[index];

			for(int i = 0;i<root->child.size();i++)
			{
				Find_Empty_Node(root->child[i]);
				index = i;
			}
	}
	return tree;
}

and then back where is called do something like this?

node* curr = root;
curr = Find_Empty_Node(node* root);

The first real problem I see is that your function takes in a node pointer you call root however if this node is empty or it's data is set to zero you are returning the first child of a node pointed to by tree . I believe you really want a statement like return root->child[index]; .
If you are trying to find a node with data set to 0 do you want to return that so it can be changed to some other data. If this is the case you should actually be returning something like return root; that way that node can be changed to some other data. If you don't change the data in the first node that has data 0 your Find_Empty_Node function will always stop at the same node and over write it's first child.
Also it would be helpful if we knew what results you were trying to get. I hope some of this helps you.

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.