# LeetCode: 701. 二叉搜索树中的插入操作¶

## 1、题目描述¶

    4
/ \
2   7
/ \
1   3


     4
/   \
2     7
/ \   /
1   3 5


     5
/   \
2     7
/ \
1   3
\
4


## 2、解题思路¶

• 递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return TreeNode(val)

if val > root.val:
root.right = self.insertIntoBST(root.right, val)
else:
root.left = self.insertIntoBST(root.left, val)

return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return TreeNode(val)

def dfs(node, father, value):
if not node:
if value > father.val:
father.right = TreeNode(value)
else:
father.left = TreeNode(value)

if value > node.value:
dfs(node.right, node, value)
else:
dfs(node.left, node, value)