LeetCode : 701. Insert into a Binary Search Tree

[congr]

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

[congr]

O(H) => O(LogN)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        insert(root, val);   

        return root;
    }

    void insert (TreeNode root, int val) {
        if (root == null) return;

        if (root.val < val) {
            if (root.right == null) root.right = new TreeNode(val);
            else insert(root.right, val);
        } else {
            if (root.left == null) root.left = new TreeNode(val);
            else insert(root.left, val);
        }
    }
}

[congr]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (root.val < val) root.right = insertIntoBST(root.right, val);
        else root.left = insertIntoBST(root.left, val);

        return root;
    }
}