Insert Node in a Binary Search Tree

Source

• lintcode: Insert Node in a Binary Search Tree

Given a binary search tree and a new tree node, insert the node into the tree. 
You should keep the tree still be a valid binary search tree.

Example
Given binary search tree as follow, after Insert node 6, the tree should be:

  2             2
 / \           / \
1   4   -->   1   4
   /             / \ 
  3             3   6
Challenge
Can you do it without recursion?

Python

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of the binary search tree.
    @param node: insert this node into the binary search tree.
    @return: The root of the new binary search tree.
    """
    def insertNode(self, root, node):
        # write your code here
        if root is None:
            return node
        if node is None:
            return root;

        cur = root 
        while cur:
            if cur.val <= node.val and cur.right is None:
                cur.right = node
                break
            elif cur.val > node.val and cur.left is None:
                cur.left =node
                break
            elif cur.val <= node.val:
                cur=cur.right
            else:
                cur=cur.left
        return  root