searching for an element in BST

Question

Following is the code for searching an element in BST. can anyone please explain what &(*cur)->right or &(*cur)->left means in the code?

Thank You

TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        TreeNode **cur = &root;
        while( *cur )
            cur = (val > (*cur)->val) ? &(*cur)->right : &(*cur)->left;
        *cur = new TreeNode(val);
        return root;
    }

You should write your own code for a BST rather than trying to understand other people's code. — Thomas Matthews, Apr 16 '20 at 19:26
See [this](https://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list) for an explanation. — cigien, Apr 16 '20 at 19:28

score 1 · Accepted Answer · answered Apr 16 '20 at 19:29

cur is a pointer to pointer, thus, to access its children, you need to dereference it (*cur) and only then access the element (->left, ->right).

After you got the next element (right or left), which is a pointer, you need to store it in cur. But cur is a pointer to pointer, so you need to take a reference of if (using the & operator).

The overall expression is the ugly &(*cur).

By the way, the reason you need a pointer to pointer, is because of the line *cur = new TreeNode(val);.

If you would simply use a pointer, this line would do nothing, and only change your temporary pointer. Since you are using a pointer to pointer, you are changing the original node in the tree.

score 0 · Answer 2 · answered Apr 16 '20 at 19:31

0

Those properties are right and left children of the current node. and the while traverses the tree to find the suitable place for the value as its bigger or less than current node as the Binary Search Tree definition

answered Apr 16 '20 at 19:31

Amin Rezaei

376
2
11

searching for an element in BST

2 Answers2