LeetCode Day 17 Binary Tree Part 7

701. Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

The number of nodes in the tree will be in the range [0, 104].
-108 <= Node.val <= 108
All the values Node.val are unique.
-108 <= val <= 108
It's guaranteed that val does not exist in the original BST.
Original Page

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            root = new TreeNode(val);
            return root;
        }
        if(root.val<val){
            root.right = insertIntoBST(root.right, val);
        }else{
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }

450. Delete Node in a BST

* Wrong Code

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return root;
        }

        TreeNode parent = root;
        TreeNode cur = root;
        boolean isLeft = false;

        while(cur!=null){
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
                isLeft = true;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
                isLeft = false;
            }
            // Main logic I will move all key's right node to replace pre-key position logic also we can do it with left node but not here
            else{
                //1. leaf node
                if(cur.left == null && cur.right == null){
                     parent = linkToParent(parent, null, isLeft,root==cur);
                } 
                else if(cur.right == null){
                        parent = linkToParent(parent, cur.left, isLeft,root==cur);
                }
                else if(cur.left == null){
                        parent = linkToParent(parent, cur.right, isLeft,root==cur);
                }
                // long logic for delete when key has both left and right child
                else{
                    if(cur.right.left == null){
                        cur.right.left = cur.left;
                        parent = linkToParent(parent, cur.right, isLeft,root==cur);
                    }
                    else{
                        TreeNode rightParent = cur.right;
                        TreeNode leftest = cur.right;
                        while(leftest.left !=null){
                            rightParent = leftest;
                            leftest = leftest.left;
                        }
                        // main logic
                        parent = linkToParent(parent, leftest, isLeft,root==cur);
                            leftest.left = cur.left;
                            leftest.right = cur.right;
                        // now we find the least element in element's right subtree 
                        if(leftest.right == null){
                            rightParent.left = null;

                        }
                        // the least element in right subtree has right child
                        else{
                            rightParent.left = leftest.right;
                        }
                    }
                }

            }
                break;
            }
            return root;
        }

    public TreeNode linkToParent(TreeNode parent, TreeNode replace, boolean isLeft, boolean isRoot){
        if(isRoot){
            parent = replace;
        }else{
            if(isLeft){
                parent.left = replace;
            }else{
                parent.right = replace;
            }
        }

        return parent;
    }