# 85.Insert Node in a Binary Search Tree

## 1.Description(Easy)

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.

### Notice

You can assume there is no duplicate values in this tree + node.

**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**](https://www.lintcode.com/en/problem/insert-node-in-a-binary-search-tree/#challenge)

Can you do it without recursion?

## 2.Code

<http://www.code123.cc/docs/leetcode-notes/binary_search_tree/insert_node_in_a_binary_search_tree.html>

**Version 1:Recursion**

二叉树的题使用递归自然是最好理解的，代码也简洁易懂，缺点就是递归调用时栈空间容易溢出，故实际实现中一般使用迭代替代递归，性能更佳嘛。不过迭代的缺点就是代码量 稍(很)大，逻辑也可能不是那么好懂。

既然确定使用递归，那么接下来就应该考虑具体的实现问题了。在递归的具体实现中，主要考虑如下两点：

1. 基本条件/终止条件 - 返回值需斟酌。
2. 递归步/条件递归 - 能使原始问题收敛。

首先来找找递归步，根据二叉查找树的定义，若插入节点的值若大于当前节点的值，则继续与当前节点的右子树的值进行比较；反之则继续与当前节点的左子树的值进行比较。题 目的要求是返回最终二叉搜索树的根节点，从以上递归步的描述中似乎还难以对应到实际代码，这时不妨分析下终止条件。

有了递归步，终止条件也就水到渠成了，若当前节点为空时，即返回结果。问题是——返回什么结果？当前节点为空时，说明应该将「插入节点」插入到上一个遍历节点的左子节 点或右子节点。对应到程序代码中即为`root->right = node`或者`root->left = node`. 也就是说递归步使用`root->right/left = func(...)`即可

```
public TreeNode insertNode(TreeNode root, TreeNode node) {
        if(root==null){
            return node;
        }
        if(root.val>node.val){
            root.left=insertNode(root.left,node);
        }else{
            root.right=insertNode(root.right,node);
        }
        return root;
    }
```

**Version 2: Iterative**

迭代比较当前节点的值和插入节点的值，到了二叉树的最后一层时选择是链接至左子 结点还是右子节点。

```
public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) return node;
        if (node == null) return root;

        TreeNode rootcopy = root;
        while (root != null) {
            if (root.val <= node.val && root.right == null) {
                root.right = node;
                break;
            }
            else if (root.val > node.val && root.left == null) {
                root.left = node;
                break;
            }
            else if(root.val <= node.val) root = root.right;
            else root = root.left;
        }
        return rootcopy;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/2.binary-tree/85insert-node-in-a-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.