# Leetcode 701. Insert into a Binary Search Tree
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/insert-into-a-binary-search-tree/ 。

想法 :

比根小往左走，比根大往右走。

時間複雜度 : O(n)。

程式碼 :

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) { 
        if(root!=nullptr){
            if(root->val <= val){
                root->right = insertIntoBST(root->right, val);
            }
            else{
                root->left = insertIntoBST(root->left, val);
            }
        }
        else{
            root=new TreeNode();
            root->val=val;
        }
        
        return root;
    }
};