MHB How can we add a node in a tree?

[evinda]

In your opening post it says that you have "a node $e$" instead of a node with key $e$.
So it should be like: [m]node->left=e[/m]. (Wasntme)

But at the original exercise, it says that it is a node with key $e$.. (Wasntme) (Blush)

 

[I like Serena]

But at the original exercise, it says that it is a node with key $e$.. (Wasntme) (Blush)

Hmm.
But doesn't that still mean you are given a "node"?
Suppose you are given a [m]nodeWithKeyE[/m] that has key $e$, then you should do:
[m]node->left = nodeWithKeyE[/m]
(Wink)

 

[evinda]

Hmm.
But doesn't that still mean you are given a "node"?
Suppose you are given a [m]nodeWithKeyE[/m] that has key $e$, then you should do:
[m]node->left = nodeWithKeyE[/m]
(Wink)

So, will this node have a struct with the key, and with a pointer to the left and the right child? (Thinking)

 

[evinda]

And what if the level $l$ does not exist? Do have to check this case? (Thinking)

 

[I like Serena]

So, will this node have a struct with the key, and with a pointer to the left and the right child? (Thinking)

We can assume the node will be a struct with a key.
I would also assume that the left and right child have been initialized to NULL. (Nerd)

And what if the level $l$ does not exist? Do have to check this case? (Thinking)

Yes. We have to ensure the algorithm can also handle that. (Wink)

 

[evinda]

We can assume the node will be a struct with a key.
I would also assume that the left and right child have been initialized to NULL. (Nerd)

So, do we have to do it with this command: [m] node->left->key=e [/m] ? (Thinking)

Yes. We have to ensure the algorithm can also handle that. (Wink)

How could we do this? (Thinking)

 

[I like Serena]

So, do we have to do it with this command: [m] node->left->key=e [/m] ? (Thinking)

No. (Shake)
When we want to add the node with key $e$ as a left child of [m]node[/m], at that point in time [m]node->left[/m] will be equal to NULL.
If we try to access [m]node->left->key[/m] in any way, we will be redirected to chaos and madness. (Devil)

How could we do this? (Thinking)

What will happen now if level $l$ does not exist? (Wondering)

 

[evinda]

No. (Shake)
When we want to add the node with key $e$ as a left child of [m]node[/m], at that point in time [m]node->left[/m] will be equal to NULL.
If we try to access [m]node->left->key[/m] in any way, we will be redirected to chaos and madness. (Devil)

So, should it be [m] node->left=e [/m] ? (Thinking)

What will happen now if level $l$ does not exist? (Wondering)

Do we have to add maybe the command of the line 11? Or am I wrong? (Worried)

1.depth=0
2.Add_node_leftmost_at_least_at_level(node, l, e)

3.  if node == NULL
4.    return failure

5.  if depth >= l and node->left == NULL
6.    node->left = e
7.    return success
8.  else if depth >= l and node->right == NULL
9.    node->right = e
10.    return success

   else
11.[B] if (node->left==NULL and node->right==NULL and depth<l) return failure;[/B]
12.  depth=depth+1
13.  result = Add_node_leftmost_at_least_at_level(node->left, l, e)
14.  if result is failure
15.    result = Add_node_leftmost_at_least_at_level(node->right, l, e)
16.  depth=depth-1
17.  return result

 

[I like Serena]

So, should it be [m] node->left=e [/m] ? (Thinking)

Let's stick with that yes. (Nod)
For the purpose of our algorithm, we will require that the parameter $e$ is a node with whatever key, that has both a left and a right child of NULL.
We should state this as a precondition of the algorithm. (Mmm)

Do we have to add maybe the command of the line 11? Or am I wrong? (Worried)

That won't be necessary.
If we leave line 11 out, the algorithm will make a recursive call, and in line 3 it will be detected that we can't get to level $l$, so the algorithm will fail in line 4.
The behavior will be the same with or without line 11. (Nerd)

 

[evinda]

That won't be necessary.
If we leave line 11 out, the algorithm will make a recursive call, and in line 3 it will be detected that we can't get to level $l$, so the algorithm will fail in line 4.
The behavior will be the same with or without line 11. (Nerd)

So what can we do elsewhise for the case that there are no more nodes in level $l$? I haven't understood it... (Sweating)

 

[I like Serena]

So what can we do elsewhise for the case that there are no more nodes in level $l$? I haven't understood it... (Sweating)

I believe there is nothing else to do.
As it is now, the algorithm will already return a failure. (Thinking)

But don't take my word for it!
What if you program the algorithm in C and apply it to a tree that has no level $l$? (Wondering)