# coding: utf-8

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 root.val > node.val:

root.left = self.insertNode(root.left, node)

else:

root.right = self.insertNode(root.right, node)

return root

# easy: http://lintcode.com/problem/insert-node-in-a-binary-search-tree