CODEWITHSUNDEEP
cparentnodesbinary-search-tree
user3195991
user3195991

Reputation: 79

Need help understanding parent nodes in binary search trees

The below code is a function that inserts a node into the correct location in the tree. What I don't understand is what the parent node actually represents. When it says root -> left -> parent = root -> left, what does it mean? Isn't that setting root's left's parent to be itself? Shouldn't it be root -> left -> parent = root instead, because we want root's left-child's parent to be root and not left-child itself? Can you please clarify parent nodes for me, Thank you.

Node * insert(Node *root, int item) {
  if (root == NULL)
    return newNode(item);

  if (item <= root -> info)
    if (root -> left == NULL) {
      root -> left = newNode(item);
      root -> left -> parent = root -> left;      //**line of interest**
    }
    else
      insert(root -> left, item);
  else
    if (root -> right == NULL) {
      root -> right = newNode(item);
      root -> right -> parent = root -> right;
    }
    else
      insert(root -> right, item);
  return root;
}

Upvotes: 0

Views: 959

Answers (1)

Shubhashis
Shubhashis

Reputation: 10631

According to your description i think the node class will be,

class node{
   int info;
   node *left;
   node *right;
   node *parent;
};

Now in BST there will be a root node in which the parent will be NULL. Suppose we insert the first value.(let it be 5)
Now root has 5 obviously. root->left is null and root->right is null.

If you insert 2 now then 2 will be in left side of the root.

so root->left will be 2. Now lets simplify this, as by root->left we mean a node, not a value. Thus root->left->info = 2;. Now there is one more thing to do. We set the value of root->left. Now what is the parent of root->left? That will be root, so root->left->parent = root;

Now if you insert another data (let it be 1) then

root->left->left->info = 1;
root->left->left->parent = root->left;

So your code did not simplify things for inserting a node in BST.

What I would do is, 

 Node n = new node();
 n = newNode(item); //as you wrote
 n->parent = root->left.

Upvotes: 1

Related Questions