Why is a double pointer necessary?

[cppnoob25]

So I've been practicing on recursion and writing a binary tree but after some input I was told I needed a double pointer for inserting. Oh and I know my print function is terrible. I haven't got to tree traversal yet.



Btree.h

class BTree{

private:

    struct Node{
        Node * left;
        Node * right;
        int data;
    };

    Node * root;

    void insert(Node ** t, const int &x);

public:
    BTree();
    void insert(const int &x);
    void print();


};

BTree.cpp

#include <iostream>
#include "BTree.h"

using namespace std;

BTree::BTree()
{
    root = nullptr;
}

void BTree::insert(const int &x)
{
    insert(&root, x);
}

void BTree::insert(Node ** t, const int &x)
{
    Node * n = new Node;
    n->left = nullptr;
    n->right = nullptr;
    n->data = x;

    if(*t == nullptr)
    {
        *t = n;
    }
    else
    {
        if(x > (*t)->data)
        {
            insert(&((*t)->right), x);
        }
        else
        {
            insert (&((*t)->left), x);
        }
    }
}

void BTree::print()
{
    cout << root->data << endl;
    cout << root->right->data << endl;
    cout << root->left->data << endl;
    cout << root->left->left->data;
}

main.cpp

#include <iostream>
#include "BTree.h"

using namespace std;

int main()
{
    BTree a;
    a.insert(5);
    a.insert(6);
    a.insert(4);
    a.insert(1);
    a.print();

}

And this is the piece of code I question and don't understand.

void BTree::insert(Node ** t, const int &x)

Why can't I use a single pointer?

[kbw]

t is being changed so it has to be passed by reference.

You can make the parameter a reference (to a pointer) or pass the address of the pointer, which is **.

[JLBorges]

This leaks:

void BTree::insert(Node ** t, const int &x)
{
    Node * n = new Node; // what happens if( *t != null ) ?
    n->left = nullptr;
    n->right = nullptr;
    n->data = x;

    if(*t == nullptr)
    {
        *t = n;
    }
    else
    {
        if(x > (*t)->data)
        {
            insert(&((*t)->right), x);
        }
        else
        {
            insert (&((*t)->left), x);
        }
    }
}

Use 'reference to pointer to Node'; the code looks much cleaner:

#include <iostream>

class BTree{

    private:

        struct Node{

            Node* left = nullptr ;
            Node* right = nullptr ;
            int data ;
            explicit Node( int v ) : data(v) {}
        };

        Node* root = nullptr ;

        void insert( Node*& t, int x )
        {
            if( t == nullptr ) t = new Node(x);
            else if( x > t->data ) insert( t->right, x ) ;
            else insert( t->left, x ) ;
        }

        void do_print( const Node* n ) const // in order
        {
            if( n != nullptr )
            {
                do_print( n->left ) ;
                std::cout << n->data << ' ' ;
                do_print( n->right ) ;
            }
        }

    public:
        void insert( int x ) { insert( root, x ) ; } // *** pass by value
        void print_in_order() const { do_print(root) ; std::cout << '\n' ; } // *** const
};

int main()
{
    BTree a ;
    for( int v : { 5, 6, 4, 1, 8, 7, 3, 9, 2 } ) a.insert(v) ;
    a.print_in_order() ;
}

http://coliru.stacked-crooked.com/a/df7aa3ecaf1a3a3c

[cppnoob25]

Hey JLBlorges I do like your cleaner code and I have a question.

When would *t not ever be null? I thought the else statement took care of that moving down the tree until it found a Nullptr?

Also I like how simple the in order traversal is. Are all the traversal methods that simple?

void BTree::insert(Node ** t, const int &x)
{
    Node * n = new Node; // what happens if( *t != null ) ?
    n->left = nullptr;
    n->right = nullptr;
    n->data = x;

    if(*t == nullptr)
    {
        *t = n;
    }
    else
    {
        if(x > (*t)->data)
        {
            insert(&((*t)->right), x);
        }
        else
        {
            insert (&((*t)->left), x);
        }
    }
}

[JLBorges]

> I thought the else statement took care of that moving down the tree until it found a Nullptr?

Each time you move down one level, insert() is called recursively; each time insert() is called a new Node is created.


> Are all the traversal methods that simple?

Depth-first traversals are all that simple.
Breadth-first traversals are more involved.
https://en.wikipedia.org/wiki/Tree_traversal


Now try writing the other foundation operations: destructor, copy constructor, copy assignment (move constructor and move assignment may be defaulted).

[cppnoob25]

Oh, I see that now. That's a potential huge memory leak.

Thanks for the direction of my study. I will get to those and probably be back for feedback.