CODEWITHSUNDEEP
cgraphtreebinary-search-tree
Serus
Serus

Reputation: 362

Why a lot of BST functions returns the root and don't use double pointer?

I'm writing a BST library that uses a lot of recursive functions that can potentially modify the root of the tree. I noticed that a lot of programmers, even on StackOverflow, often return the root node when a function could potentially modify it.

Why this practice is so diffuse? Use a double pointer to do the same thing isn't good?

I searched online and found nothing :/

Upvotes: 0

Views: 55

Answers (1)

John Bollinger
John Bollinger

Reputation: 181104

Why this practice is so diffuse? Use a double pointer to do the same thing isn't good?

It's largely a question of style and preferences.

Using a double pointer permits the function to modify the root pointer itself, which I consider advantageous, but it means that your code has to deal with multiple levels of indirection at the same time, which some people find confusing or distasteful.

Returning the new root allows keeping to a single level of indirection, but it places an extra burden on all users of functions that mutate the tree: they must update the root pointer with the value returned by the function. This also means that if the function also wants to return something else as well, then you need an out parameter, or a structure for a return type, or similar, which loses much of the simplicity gained.

Personally, I prefer none of the above. Rather than working with a bare root pointer, I prefer to put the root pointer into a container structure, possibly with other general data about the tree, and pass pointers to that to methods. Although technically that's still two levels of indirection, it looks and feels more like one, and it allows the functions involved to update the root pointer themselves. Example,

struct node {
    int data;
    struct node *left,
    struct node *right;
};

struct tree {
    struct node *root;
    // ... maybe other members ...
};

void insert(struct tree *tree, int data) {
    // ... perform insertion, ultimately finishing with
    tree->root = new_root;
}

Of course, it makes recursive function implementations a little (not much) tricker, but recursion is often a poor choice for real-world programs.

Upvotes: 2

Related Questions