How to write the code for 'addToRightMostChildAsLeftChild(Node a,Node b)'?

Question

Lets say the above method has two arguments a and b:

• a : represents the root node of the tree for which we need to traverse till we get the right node
• b : represents the node to be added to a's right most node as a left child.

I just need to know how to add a `node to the right most node of the tree but as a left child. I'm actually solving a different version of this problem. Here the problem is using right pointers.

Construct a tree in such a way that traversing it only through left pointers generates pre-order traversal of the tree.

Actually it can be solved by traversing the tree and maintaining a previous node and linking them in the way we want :prev.left = current`.

My way of approaching this problem was: If there's a tree as following

(just add the node 2 to 5 as a left child and then 5 to 3 as left child and finally 6 to 4 as left child.)

                 10
                 / \
                8   2
               / \ / \
              3  5 4  6


               10
               /
              8
             / \
            3   5
               /
              2
             / \
            4   6

             10
             /
            8
           / 
          3
         /
        5
       /
      2 
     / \
    4   6
             10
             /
            8
           / 
          3
         /
        5
       /
      2
     /
    4
   /
  6

10 8 3 5 2 4 6 which is the pre-order traversal of the tree

I know it can be done by using `prev pointer and doing stuff. I want it do be done this way.

                 10        
                 / \
                8   2      
               / \ / \
              3  5 4  6

                 ||
                 \/

                10
               /
              8
             / 
            3
           /
          5
         /
        2
       /
      4
     /
    6

Node is defined as:

 class Node{
    int data;
    Node left,right;
    Node(int d)
    {
        data=d;
        left=null;
        right=null;
    }
}

Answer 1

After giving it some thought I am able to do it.

void addToRightMostNodeAsLeftChild(Node root,Node toBeAdded)
{
    if(root.left==null)
    {
        root.left=toBeAdded;
    }
    else
    {
        Node k=getRMNode(root.left);
        if(k.left==null)
        {
            k.left=toBeAdded;
        }
        else
            addToRightMostNodeAsLeftChild(k, toBeAdded);
    }
    root.right=null;
}

So, When I want to place node 2 as a left child of 5 which is the right-most node of node 8 (adding as a left child to the right most node of some XYZ node XYZ being 8 here ) When the method is called as follows:

addToRightMostNodeAsLeftChild(root,X) /*root represents node 10 and X represents node 2*/

it gets converted to:

           10
           /
          8
         / \
        3   5
           /
          2
         / \
        4   6