How to construct tree in this question as we also need to manage parent pointer?

#1

We have to manage parent pointer in this question? How do we construct tree?

#2

@ikshuldureja130 see when u given an array traverse that array create a node for first element from array and put in it and make as root then whenever element comes you hae to make node and according to property of BST u have to put

#3

@ikshuldureja130 like in array 5 1 3 4 2 7 u have to make first node as root from first element of array i.e 5 then further traversel according to property of BST u have to arrange or construct
5
/
1 7

3
/
2 4

srry for bekar diagram :slight_smile:

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

preorder method is to create tree…but after that i need to set parent pointer of each node…how do i do that?

#6

but preorder is for print you have to traverse array via for loop then create node and go recursively to left and right @ikshuldureja130

#7

yes but after building tree, I need to set parent pointer for every node (parent pointer basically points to parent of each node)…how do I do that?..please see the question to know why I need to set parent pointer for each node…because it is asked in the question

#8

@ikshuldureja130

You just need to update the BST insert function by updating the parent pointer of the node to be inserted in each comparison.

for example, if the current BST is :
explain

Now if we try to insert 16,

  1. create a new node with its data = 16 and parent as null
  2. first comparison is with 9, as (9<16) we move to the right subtree and update the parent of 16 to be 9(cur node).
  3. second comparison is with 15, as (15<16) we move to the right subtree and update the parent of 16 to 15(cur node).
  4. In last comparison we are at null, so our recursive call ends here.

Code:
`
insert(Node* root, int data){
if (root == NULL){
//return a new node with value = data
}
Node* temp;
if (data <= root->data) {
temp = insert(root->left, data);
root->left = temp;
}
else {
temp = insert(root->right, data);
root->right = temp;
}
temp->parent = root;
return root;

}
`

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.