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
6
Views
9 Years
Discussion Span
Last Post by rcollins
``````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.

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.

``````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.

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.

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.