use of double pointer instead of single pointer

Question

I am working on a Binary search tree.

So,here is the structure used for representing the node:

typedef struct TreeNode
{
int num;
struct TreeNode *left,*right;
}TREENODE;

To insert a node in the tree I have the following method signatire

void InsertNode(TREENODE **root,int data);

In the above method why do we require double pointer.We can use a single pointer!

Are we using double pointer to avoid duplication?

@Anirudha. Ok, I'm glad to see you questioning your teachers!! — Nick, Feb 21 '12 at 16:33

Andrey · Accepted Answer · 2012-02-21T16:37:33.797

7

No, this is needed in case of rebalancing. After rebalancing root could be changed.

Ok, I will expand. Double pointer allows you to modify the pointer. So what is tree root in your case? Pointer to TREENODE. Some operations like search will never modify it. But some operations might need to change it, so that another node becomes new root. So they have to have access to that variable that you use as root. One example why they might need it is rebalancing, see AVL trees.

edited Feb 21 '12 at 16:37

answered Feb 21 '12 at 16:29

Andrey

59,039
12
119
163

2

this. When you use a pointer, the root node would always point to the node you have given as an argument. but when by some balancing , the root node changes, your pointer to the root needs to change too. Thats why you need a pointer to a pointer. (root is not only an input variable here but an output varaible too) – Hayt Feb 21 '12 at 16:35
It is not necessarily "rebalancing". Who said there's any rebalancing implemented there? It could be the mere fact that the very first insertion into an empty tree will change the root from null pointer to a non-null pointer. – AnT stands with Russia Jun 29 '13 at 05:46
@AndreyT it is was an example. So nobody "there's any rebalancing implemented there". – Andrey Jun 29 '13 at 14:06

score 2 · Answer 2 · answered Feb 21 '12 at 16:30

2

If we need double pointer, then we need to modify the pointer it points to.

answered Feb 21 '12 at 16:30

Michael Krelin - hacker

138,757
24
193
173

score 2 · Answer 3 · answered Feb 21 '12 at 16:33

2

No -- you're using a double point so you can modify a pointer.

answered Feb 21 '12 at 16:33

Jerry Coffin

476,176
80
629
1,111

score 0 · Answer 4 · edited May 23 '17 at 12:06

0

Use of "Double pointers" allow you to change Content of memory that <some_class>* holds address of. So, we're basically preserving state of Memory location even outside function call. Another use is like for e.g. char* (as String), and char** (as Array of String)

You may find my reply in another thread: Why use double pointer? or Why use pointers to pointers?

edited May 23 '17 at 12:06

Community

1
1

answered Jun 29 '13 at 05:42

bharat1

103
1
13

score 0 · Answer 5 · answered Feb 21 '12 at 16:30

0

It's very depend on how do you use the tree. if the tree should keep on some kind of sorting, so insertion can change the root node, so you need double pointer.

answered Feb 21 '12 at 16:30

asaelr

5,438
1
16
22

use of double pointer instead of single pointer

5 Answers5