Question: We have to make the tree in-order traversal such that it only have right side node. All the left nodes will be null (no left nodes).

The Question in Leetcode

Pseudo Code

• First step is we have to check whether the node came is null or not. If it is null then return the null as response.
• Then once it is null, we have to do as in IN-order travesal.
• We have to do the recursive call, convert the left side sub-tree into increasingBST; then call it leftTree and recursively do it for right side sub-tree rightTree.
• After that, we have to find out the last node from left side sub-tree; this node will be used to attach the right side sub-tree. Lets call it leftEndNode
• We have make the current node's left node as null, we have already got the sub-tree from that node and saved in leftTree.
• Then we have to append the current node's right node from the right sub-tree we got before.
• If we have got the left sub-tree's last node as not null, then to that node we have to set the right value as current node (remember current node's right value is right sub-tree; so it is appeneded), then we have to return the left sub-tree root node.
• If we have got the left sub-tree's last node as null, then it means there is no left sub-tree. At that time we have to send the current root node.

To Find the last node in the left sub tree.

• We have to first send the root node of left sub tree.
• Iterate it till the current node and current node's right is not null.
• Each time we have to reset the current node value current node's right.

Java Code

 public TreeNode increasingBST(TreeNode root) {
TreeNode currentNode = root;
 if (currentNode != null){
    TreeNode leftTree = increasingBST(currentNode.left);    
    TreeNode rightTree = increasingBST(currentNode.right);

    TreeNode leftEndNode = findLastRightNode(leftTree);

    currentNode.left = null;
        currentNode.right = rightTree;
    if(leftEndNode != null){
        leftEndNode.right = currentNode;
            return leftTree;
    }
        return currentNode;
}  // end of current node null check
return null;
} // end of method

public static TreeNode findLastRightNode(TreeNode leftTree){
    TreeNode currentNode = leftTree;
         while(currentNode != null && currentNode.right!=null){
               currentNode = currentNode.right;
         }
         return currentNode;

}