/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	TreeNode newNode = null;
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    	newNode = new TreeNode(val);
    	return helper(root);
    }
    public TreeNode helper(TreeNode root)
    {
    	if(root == null)
    		return null;

    	if(root.val < newNode.val)
    	{
    		newNode.left = root;
    		return newNode;
    	}
    	if(root.right != null)
    		root.right =  helper(root.right);
    	else
    		root.right = newNode;
    	return root;
    }
}