C - tree insertion into specific position

0
votes

I want to write a function to add a node to a tree which takes as parameters the root, the value of the node, the value of the node below which I want to add the new node and a number according to which I will add the node to be left or right child (even = right child, odd = left child). I don't understand where I wrong , its the same concept of BST just other condition. I would appreciate any help.

for example :

                             6
                            / \
                          3    20

Tnode* insert (Tnode* root , int data , int father , int leftOrRight) ; insert (root , 50 , 6 , 2) the tree will be :

                           6
                          / \
                         3   50
                              \
                               20

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
            if (leftOrRight % 2 == 0)
                root->right = insert(root->right , data , father , leftOrRight);
            else
                root->left = insert(root->left , data , father , leftOrRight) ;
    return root ;
}

 Tnode* newNode(int data)
{
    Tnode* node = (Tnode*)malloc(sizeof(Tnode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
2
calgorithmrecursiontree
When you find the father, you can create a new node and insert it left or right and don't recurse further unless you want to insert it at the leaf. I think thats where it is going wrong. - rootkonda

2 Answers

0
votes

First thing the code you have written is checking only for the root of the tree to be father. I am assuming you are trying to check the whole tree. So you need to call recursively the insert function for both its left and right child to search the whole tree for the father.

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
            if (leftOrRight % 2 == 0)
                root->right = insert(root->right , data , father , leftOrRight);
            else
                root->left = insert(root->left , data , father , leftOrRight) ;
    insert(root->left , data , father , leftOrRight);
    insert(root->right, data , father , leftOrRight); 
    return root; 
}

 Tnode* newNode(int data)
{
    Tnode* node = (Tnode*)malloc(sizeof(Tnode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
0
votes

You don't need recursion if you have already found the node at which the data should be entered.

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
    {
        Tnode * node = newNode(data);
        if (leftOrRight % 2 == 0)
        {
           node -> left = root -> right; // can be node -> right as well
           root -> right = node;
        }
        else
        {
           node -> left = root -> left; // can be node -> right as well
           root -> left = node;
        }
    }
    else
    {
       // if the current node is not the required node check the leaves
       insert(root->left , data , father , leftOrRight);
       insert(root->right, data , father , leftOrRight);
    }
    return root; 
}