Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /*
- Iterative Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(1)
- N = Total number of nodes in the binary search tree.
- */
- class Solution {
- public TreeNode insertIntoBST(TreeNode root, int val) throws IllegalArgumentException {
- if (root == null) {
- return new TreeNode(val);
- }
- TreeNode cur = root;
- while (true) {
- if (val == cur.val) {
- throw new IllegalArgumentException("val already exists in the given binary search tree");
- }
- if (val > cur.val) {
- if (cur.right != null) {
- cur = cur.right;
- } else {
- cur.right = new TreeNode(val);
- break;
- }
- } else {
- if (cur.left != null) {
- cur = cur.left;
- } else {
- cur.left = new TreeNode(val);
- break;
- }
- }
- }
- return root;
- }
- }
- /*
- Recursive Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(H)
- N = Total number of nodes in the binary search tree.
- H = Height of the tree (Recursion Stack).
- */
- class Solution {
- public TreeNode insertIntoBST(TreeNode root, int val) throws IllegalArgumentException {
- if (root == null) {
- return new TreeNode(val);
- }
- if (val == root.val) {
- throw new IllegalArgumentException("val already exists in the given binary search tree");
- }
- if (val > root.val) {
- root.right = insertIntoBST(root.right, val);
- } else {
- root.left = insertIntoBST(root.left, val);
- }
- return root;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement