Member Avatar for nhrnjic6

In function :

node* insert_in_tree(int number,node* p_tree) {

   if(p_tree == 0) {

    node* newNode = new node;
    newNode->num = number;
    newNode->p_left = 0;
    newNode->p_right = 0;
    return newNode;

    }

    if(number < p_tree->num) {

     p_tree->p_left = insert_in_tree(number,p_tree->p_left);

     }

     else {

        p_tree->p_right = insert_in_tree(number,p_tree->p_right);

     }

      return p_tree; // refering to this

 }

        in return p_tree is it returning newly created node, or a root node ?
  • 2 Contributors
  • 1 Reply
  • 192 Views
  • 12 Minutes Discussion Span
  • Latest Post Latest Post by rubberman

Dani AI

Generated

Short answer: the function returns the root pointer for the subtree handled by that call. If the call finds p_tree == 0 it constructs a new node and returns that pointer (so that call's subtree root is the newly created node). If p_tree was non-null the function returns the same p_tree pointer you passed in — but with its left or right child updated by the recursive return. The top-level call therefore returns either the original tree root or a new root when the tree was empty.

Why that return is necessary: C++ passes the pointer by value, so assigning to the local p_tree inside the function does not change the caller’s variable. Returning the pointer and assigning it at the call site is how the newly-created node is linked into the parent. That’s why you must write something like root = insert_in_tree(value, root); at the top level, and why recursive calls usually do p_tree->p_left = insert_in_tree(..., p_tree->p_left);.

Alternative designs and cautions: you can avoid returning a pointer by taking a reference to the pointer (void insert(node*& root, int value)), or by using smart pointers (std::unique_ptr) to express ownership and avoid leaks. For self‑balancing trees (AVL/Red‑Black) the subtree root can change during rotations, so returning the subtree root is required. Also decide how you want to treat duplicates — the original else will put equals one side; use an explicit else if (value > p_tree->num) or handle equality explicitly if duplicates must be disallowed, as suggested.

In short: the function returns whatever is the root of that subtree (new node when the subtree was empty, otherwise the same node pointer possibly with updated children). Remember to assign the returned pointer back into the caller’s variable or child link so the tree structure is preserved.

Member Avatar for rubberman

It depends upon your intention. Normally in recursive functions you would do this (assuming you don't want duplicate numbers):

node* insert_in_tree(int number,node* p_tree)
{
    if(p_tree == 0)
    {
        p_tree = new node;
        p_tree->num = number;
        p_tree->p_left = 0;
        p_tree->p_right = 0;
    }
    else if(number < p_tree->num)
    {
        p_tree->p_left = insert_in_tree(number,p_tree->p_left);
    }
    else if (number > p_tree->num)
    {
        p_tree->p_right = insert_in_tree(number,p_tree->p_right);
    }
    return p_tree; // refering to this
}

To determine if this is correct, I would have to see the rest of your code. Note that these changes allow you to keep to the optimal "1 return point per function". It also may allow the compiler to optimize the code a bit better.

Edited by rubberman
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.