How can we add a node in a tree?

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Tree
In summary: Finally attach e as either the left child or right child of p.Just to make certain that I understand your question:In summary, you would add a node to a binary tree by first finding the leftmost node at a specific level, and then attaching the node to that leftmost node.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

Suppose that we have a binary tree and a specific level $l$.
I want to add in the tree, a node $e$, as a child of the leftmost node of the level $l$, if the latter hasn't two children. If the leftmost node of the level $l$ has two children, then we have to look for a leftmost node, with less than two children, at the next levels and $e$ will be the child of the first such node, that will be found.

How can we add a node in a tree? (Thinking)
 
Technology news on Phys.org
  • #2
evinda said:
Hello! (Wave)

Suppose that we have a binary tree and a specific level $l$.
I want to add in the tree, a node $e$, as a child of the leftmost node of the level $l$, if the latter hasn't two children. If the leftmost node of the level $l$ has two children, then we have to look for a leftmost node, with less than two children, at the next levels and $e$ will be the child of the first such node, that will be found.

How can we add a node in a tree? (Thinking)

Hey! (Smile)

If it's a binary tree, we should have something like:
Code: 
struct Node {
  int value;
  struct Node *left;
  struct Node *right;
};

struct Node *tree;

Suppose you have found the [m]node[/m] where you want to add a the node [m]e[/m] as a child to the left, then you can add it with:
Code: 
node->left = e;
I'm assuming here that there was no left child yet.

There you go! (Happy)
 
  • #3
You must assume there is such a node at level l. So first find the left most node at level l:

Oops. I need to think about how to find such a node. The only thing I can think of is to do a level traversal of the tree with a queue. So assume q is an initially empty queue that can store a node and an integer.

Code: 
q.add(root,0);
while (true) {
  q.remove(p,d);
  if (d == l) {
    break;
  }
  if (p.left != null) {
    q.add(p.left,d+1);
  }
  if (p.right != null) {
    q.add(p.right,d+1);
  }
}

Now p is the left most node at level l.
Next as long as node p has two children continue the above loop to find the node p where e is to be attachedt -- left to you. Finally attach e as either the left child or right child of p.

Just to make certain that I understand your question:

2upzrjp.png
 
Last edited:
  • #4
I like Serena said:
Hey! (Smile)

If it's a binary tree, we should have something like:
Code: 
struct Node {
  int value;
  struct Node *left;
  struct Node *right;
};

struct Node *tree;

Suppose you have found the [m]node[/m] where you want to add a the node [m]e[/m] as a child to the left, then you can add it with:
Code: 
node->left = e;
I'm assuming here that there was no left child yet.

There you go! (Happy)

So, should it be like that?

Code: 
Function(P,l,e){
   int i=0;
   while (i<e){
            tree->left=tree->left->next:
            tree->right=tree->right->next;
   }
   if (tree->left->next==NULL) tree->left->next=e;
   else if (tree->right->next==NULL) tree->right->next=e;
   else { 
          tree->left=tree->left->next:
          tree->right=tree->right->next;
          while (tree!=NULL){
                   if (tree->left->next==NULL) tree->left->next=e;
                   else if (tree->right->next==NULL) tree->right->next=e;
                   else tree=tree->next;
           }
    }
 }

Or am I wrong? (Thinking) Also, do we have to initialize [m]left[/m] and [m]right[/m]? :confused:

- - - Updated - - -

johng said:
You must assume there is such a node at level l. So first find the left most node at level l:

Oops. I need to think about how to find such a node. The only thing I can think of is to do a level traversal of the tree with a queue. So assume q is an initially empty queue that can store a node and an integer.

Code: 
q.add(root,0);
while (true) {
  q.remove(p,d);
  if (d == l) {
    break;
  }
  if (p.left != null) {
    q.add(p.left,d+1);
  }
  if (p.right != null) {
    q.add(p.right,d+1);
  }
}

So, is the use of a queue necessary? (Thinking)

johng said:
Now p is the left most node at level l.
Next as long as node p has two children continue the above loop to find the node p where e is to be attachedt -- left to you. Finally attach e as either the left child or right child of p.

Just to make certain that I understand your question:

Yes, that's what I mean... (Yes)
 
  • #5
evinda said:
Code: 
Function(P,l,e){
   int i=0;
   while (i<e){
            tree->left=tree->left->next:
            tree->right=tree->right->next;
   }
   if (tree->left->next==NULL) tree->left->next=e;
   else if (tree->right->next==NULL) tree->right->next=e;
   else { 
          tree->left=tree->left->next:
          tree->right=tree->right->next;
          while (tree!=NULL){
                   if (tree->left->next==NULL) tree->left->next=e;
                   else if (tree->right->next==NULL) tree->right->next=e;
                   else tree=tree->next;
           }
    }
 }

What is [m]P[/m]? (Wondering)
I though [m]e[/m] was a node, so how can it be compared to the integer [m]i[/m]?
What is the data member [m]next[/m] stand for? (Wondering)
Also, do we have to initialize [m]left[/m] and [m]right[/m]? :confused:

Yes. (Nod)

If we have a tree with only a root that has value 'M', we should initialize the tree with:
Code: 
tree = malloc(sizeof(struct Node));
tree->value = 'M';
tree->left = NULL;
tree->right = NULL;
(Nerd)
So, is the use of a queue necessary? (Thinking)

I would prefer a recursive function.
It might look like:
Code: 
Add_node_leftmost_at_least_at_level(node, l, e, depth)

  /* Handle final failure case */
  if node == NULL
    return failure

  /* Handle final success cases */
  if depth >= l and node->left == NULL
    node->left = e
    return success
  if depth >= l and node->right == NULL
    node->right = e
    return success

  /* Recurse first left, then right */
  result = Add_node_leftmost_at_least_at_level(node->left, l, e, depth + 1)
  if result is failure
    result = Add_node_leftmost_at_least_at_level(node->right, l, e, depth + 1)

  return result
and it should be called with
Code: 
Add_node_leftmost_at_least_at_level(tree, l, e, 0)
(Thinking)
 
  • #6
I like Serena said:
What is [m]P[/m]? (Wondering)
I though [m]e[/m] was a node, so how can it be compared to the integer [m]i[/m]?
What is the data member [m]next[/m] stand for? (Wondering)

(Tmi)
I like Serena said:
I would prefer a recursive function.
It might look like:
Code: 
Add_node_leftmost_at_least_at_level(node, l, e, depth)

  /* Handle final failure case */
  if node == NULL
    return failure

  /* Handle final success cases */
  if depth >= l and node->left == NULL
    node->left = e
    return success
  if depth >= l and node->right == NULL
    node->right = e
    return success

  /* Recurse first left, then right */
  result = Add_node_leftmost_at_least_at_level(node->left, l, e, depth + 1)
  if result is failure
    result = Add_node_leftmost_at_least_at_level(node->right, l, e, depth + 1)

  return result
and it should be called with
Code: 
Add_node_leftmost_at_least_at_level(tree, l, e, 0)
(Thinking)

The only arguments, that the function can have, are [m]node,l,e[/m], so we have to calculate the depth in the fuction, right? (Thinking)
If so, how could we do this? :confused:
 
  • #7
evinda said:
The only arguments, that the function can have, are [m]node,l,e[/m], so we have to calculate the depth in the fuction, right? (Thinking)
If so, how could we do this? :confused:

Right! (Smile)

We can do this by adding a fourth parameter called "depth" that tracks the depth while traversing the tree.
In the initial call we specify [m]0[/m], since the first node is given to be at level 0.
Whenever we make a recursive call, we add 1 to the current depth, and pass that along to the call. (Nerd)
 
  • #8
I like Serena said:
Right! (Smile)

We can do this by adding a fourth parameter called "depth" that tracks the depth while traversing the tree.
In the initial call we specify [m]0[/m], since the first node is given to be at level 0.
Whenever we make a recursive call, we add 1 to the current depth, and pass that along to the call. (Nerd)

Is there also an other way, rather than adding a fourth parameter? (Thinking)
 
  • #9
evinda said:
Is there also an other way, rather than adding a fourth parameter? (Thinking)

We can create an extra function that wraps the recursive function that only has 3 parameters. (Thinking)

Or else we can track the depth in a global variable. (Wasntme)
 
  • #10
I like Serena said:
We can create an extra function that wraps the recursive function that only has 3 parameters. (Thinking)

How could we do this? (Thinking)

I like Serena said:
Or else we can track the depth in a global variable. (Wasntme)

I did it:

Code: 
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.  depth=depth+1
12.  result = Add_node_leftmost_at_least_at_level(node->left, l, e)
13.  if result is failure
14.    result = Add_node_leftmost_at_least_at_level(node->right, l, e)

15.  return result

Is it right? (Thinking)

I applied it at an example and I got the right result:

View attachment 3597

(Happy)

I tried to calculate the complexity of the algorithm:

At line 1, there is 1 elementary command.
At line 2, there are T(n) elementary commands.
At line 3, there is 1 elementary command.
At line 4, there is 1 elementary command.
At line 5, there are 3 elementary commands.
At line 6, there are 2 elementary commands.
At line 7, there is 1 elementary command.
At line 8, there are 3 elementary commands.
At line 9, there are 2 elementary commands.
At line 10, there is 1 elementary command.
At line 11, there are 2 elementary commands.
At line 12, there are T(n-1)+1 elementary commands.
At line 13, there is 1 elementary command.
At line 14, there are T(n-1)+1 elementary commands.
At line 15, there is 1 elementary command.So, I found that the complexity is:

$$T(n)=\left\{\begin{matrix}
2 &,n=0 \\
2T(n-1)+11 & ,n>0
\end{matrix}\right.$$

Is it right or have I done something wrong? (Thinking)
 

Attachments

  • tree10.png
    tree10.png
    3.1 KB · Views: 72
  • #11
evinda said:
How could we do this? (Thinking)

You could create a new function as follows:
Code: 
Solve_problem(node, l, e)
    result = Add_node_leftmost_at_least_at_level(node, l, e, 0)
    return result
(Wasntme)
Code: 
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.  depth=depth+1
12.  result = Add_node_leftmost_at_least_at_level(node->left, l, e)
13.  if result is failure
14.    result = Add_node_leftmost_at_least_at_level(node->right, l, e)

15.  return result

Is it right? (Thinking)

If you use a global variable, you also need to decrement depth again.
Otherwise it just keeps counting up. (Worried)
 
  • #12
I like Serena said:
You could create a new function as follows:
Code: 
Solve_problem(node, l, e)
    result = Add_node_leftmost_at_least_at_level(node, l, e, 0)
    return result
(Wasntme)

If you use a global variable, you also need to decrement depth again.
Otherwise it just keeps counting up. (Worried)

When we use a global variable, isn't the complexity better, that when we create a new function? Or am I wrong? (Thinking)

Where do we have to decrement the depth? (Thinking)
 
  • #13
evinda said:
When we use a global variable, isn't the complexity better, that when we create a new function? Or am I wrong? (Thinking)

The order of complexity doesn't change, although there is indeed an overhead that is negligible.
Good programming practice says we should avoid global variables whenever possible though. (Nerd)
Where do we have to decrement the depth? (Thinking)

The depth needs to be incremented just before making any recursive function call.
And it has to be decremented just after that recursive function call returns. (Wink)
 
  • #14
I like Serena said:
The depth needs to be incremented just before making any recursive function call.
And it has to be decremented just after that recursive function call returns. (Wink)

Could you explain me why we have to decrement the depth, after that recursive function call returns? (Thinking)
 
  • #15
evinda said:
Could you explain me why we have to decrement the depth, after that recursive function call returns? (Thinking)

When we enter the recursive function, we will be looking at a child of the current node.
The depth of the child is 1 more than the current node, so we have to add 1.

When we return from the recursive call, we are effectively back at the current node. Since we had added 1 when we went to the child, we have to subtract 1 again to have the proper depth for the current node. (Thinking)
 
  • #16
I like Serena said:
When we enter the recursive function, we will be looking at a child of the current node.
The depth of the child is 1 more than the current node, so we have to add 1.

When we return from the recursive call, we are effectively back at the current node. Since we had added 1 when we went to the child, we have to subtract 1 again to have the proper depth for the current node. (Thinking)

Code: 
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.  depth=depth+1
12.  result = Add_node_leftmost_at_least_at_level(node->left, l, e)
13.  if result is failure
14.    result = Add_node_leftmost_at_least_at_level(node->right, l, e)
15.  depth=depth-1
16.  return result

Do you mean that we have to decrement the depth in line 15? (Thinking)Also, is this command: [m] return failure [/m] only executed, when we have at the beginning a tree without nodes? (Thinking)
Or is there also an other case, in which this command is executed? :confused:
 
Last edited:
  • #17
evinda said:
Code: 
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.  depth=depth+1
12.  result = Add_node_leftmost_at_least_at_level(node->left, l, e)
13.  if result is failure
14.    result = Add_node_leftmost_at_least_at_level(node->right, l, e)
15.  depth=depth-1
16.  return result
Do you mean that we have to decrement the depth in line 15? (Thinking)

The depth should be decremented between lines 12 and 13.
Then it should be incremented again between 13 and 14.
The decrement at line 15 should be inside the "if". (Wasntme)
Also, is this command: [m] return failure [/m] only executed, when we have at the beginning a tree without nodes? (Thinking)
Or is there also an other case, in which this command is executed? :confused:

It is executed if we try to go to the child of any leaf.
If we get there, apparently we have been unable to find a place for our node.
That means we should fail, and keep returning from the recursive functions until we return from the uppermost. (Thinking)
 
  • #18
I like Serena said:
It is executed if we try to go to the child of any leaf.
If we get there, apparently we have been unable to find a place for our node.
That means we should fail, and keep returning from the recursive functions until we return from the uppermost. (Thinking)
But ... when will this happen? (Thinking)
If the node that satisfies the conditions is a leaf, don't we add then a child to this node? (Worried)
Or have I understood it wrong? :confused:
 
  • #19
evinda said:
But ... when will this happen? (Thinking)
If the node that satisfies the conditions is a leaf, don't we add then a child to this node? (Worried)
Or have I understood it wrong? :confused:

Suppose we have a leaf that is well above the requested level? (Wondering)
Then we're not supposed to add the node there, but we should keep searching for a leaf that is at a sufficiently deep level. (Wasntme)
 
  • #20
I like Serena said:
Suppose we have a leaf that is well above the requested level? (Wondering)
Then we're not supposed to add the node there, but we should keep searching for a leaf that is at a sufficiently deep level. (Wasntme)

Could you give me an example, at which the command [m] return failure; [/m] is executed? (Worried)
 
  • #21
Suppose that we want to trace the algorithm for the following tree:

https://www.physicsforums.com/attachments/3631

depth=0
Add_node_leftmost_at_least_at_level(A, 2, e)
depth=1
result=Add_node_leftmost_at_least_at_level(B, 2, e)
depth=2
result=Add_node_leftmost_at_least_at_level(D, 2, e)
depth=3
result=Add_node_leftmost_at_least_at_level(F, 2, e)=success

How do we continue? Does each [m] result [/m] from the previous recursive calls get the value [m] success [/m] ? Or what happens? (Worried)
 
  • #22
evinda said:
Suppose that we want to trace the algorithm for the following tree:

https://www.physicsforums.com/attachments/3631

depth=0
Add_node_leftmost_at_least_at_level(A, 2, e)
depth=1
result=Add_node_leftmost_at_least_at_level(B, 2, e)
depth=2
result=Add_node_leftmost_at_least_at_level(D, 2, e)
depth=3
result=Add_node_leftmost_at_least_at_level(F, 2, e)=success

How do we continue? Does each [m] result [/m] from the previous recursive calls get the value [m] success [/m] ? Or what happens? (Worried)

That is what should happen yes.
How about if the tree is balanced the other way, to the right? (Wondering)
 
  • #23
I like Serena said:
That is what should happen yes.

So, does each result from the previous recursive calls have to get the value [m]success[/m] ? (Thinking)

I like Serena said:
How about if the tree is balanced the other way, to the right? (Wondering)

If the tree has this form:

View attachment 3632

these commands will be executed:

depth=0
Add_node_leftmost_at_least_at_level(A, 2, e)
depth=1
result=Add_node_leftmost_at_least_at_level(B, 2, e)
depth=2
result=Add(NULL,2,e)
return failureright? (Thinking)Will the function terminate, only when we have return failure/success at the lines 7/8/10 ? (Thinking)
 
  • #24
evinda said:
right? (Thinking)

Will the function terminate, only when we have return failure/success at the lines 7/8/10 ? (Thinking)

Right! (Smile)

The function should not terminate, but it should backtrack and keep trying. (Thinking)
 
  • #25
I like Serena said:
The function should not terminate, but it should backtrack and keep trying. (Thinking)

Why shouldn't it terminate when we get [m]failure[/m]? (Worried)
 
  • #26
evinda said:
Why shouldn't it terminate when we get [m]failure[/m]? (Worried)

It shouldn't since we still need to find a place to add the new node. (Thinking)
 
  • #27
I like Serena said:
It shouldn't since we still need to find a place to add the new node. (Thinking)

But, in the tree of post #23, there is no leaf of which the node could be the child.. (Shake)
How will the algorithm terminate then? (Thinking)
 
  • #28
evinda said:
But, in the tree of post #23, there is no leaf of which the node could be the child.. (Shake)
How will the algorithm terminate then? (Thinking)

Couldn't it become a left child of D? (Thinking)
 
  • #29
I like Serena said:
Couldn't it become a left child of D? (Thinking)

Oh yes, you are right... (Wait) So, does this mean that we can always find a place to add the new node? (Thinking)

I reread the exercise and the algorithm should insert at the tree a node with key $e$.
So, is it right like that: [m] node->left=e[/m] or should we have something like that: [m] node->left->data=e[/m] ? (Thinking)
 
  • #30
evinda said:
Oh yes, you are right... (Wait) So, does this mean that we can always find a place to add the new node? (Thinking)

I reread the exercise and the algorithm should insert at the tree a node with key $e$.
So, is it right like that: [m] node->left=e[/m] or should we have something like that: [m] node->left->data=e[/m] ? (Thinking)

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)
 
  • #31
I like Serena said:
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)
 
  • #32
evinda said:
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)
 
  • #33
I like Serena said:
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)
 
  • #34
And what if the level $l$ does not exist? Do have to check this case? (Thinking)
 
  • #35
evinda said:
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)
evinda said:
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)
 

Similar threads

MHB Deleting Element from 2-3 Tree Example
Replies
1
Views
2K
MHB Finding Depth of Perfect & Complete Binary Trees
Replies
1
Views
2K
MHB Build Huffman Tree with Ternary System
Replies
1
Views
2K
MHB Find Next Smallest & Greatest Key in BST
Replies
1
Views
1K
MHB How Can You Check if a Binary Tree Satisfies the Properties of a 2-3 Tree?
Replies
4
Views
2K
I How do leaf nodes behave in regression decision trees?
Replies
6
Views
2K
MHB Binary Search Tree - Sort the same BSTree by name or by weight
Replies
3
Views
2K
MHB Drawing Binary Tree: Exploring Pre-Order & In-Order Traversal
Replies
14
Views
3K
Java Java- CompareTo with Binary Search Tree
Replies
3
Views
3K
MHB Efficient AVL-Tree Node Deletion: Step-by-Step Guide and Tips"
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top