Concise C# solution O(logN) time and O(1) space

  • 0

    If the root is the one to be deleted
    1) root is leave --> return null
    2) root has right --> move root.left to the left of the most left child of root.right, then return root.right
    3) root only has left --> return left

    If the root is not to be deleted --> recursively find it in either left or right branch

    public class Solution {
       public TreeNode MostLeft(TreeNode root) {
           if (root.left != null) return MostLeft(root.left);
           return root;
       public TreeNode DeleteNode(TreeNode root, int key) {
           if (root == null) return null;
           if (root.val == key) {
               if (root.left == null && root.right == null) {
                   return null;
               } else if (root.right != null)  {
                   MostLeft(root.right).left = root.left;
                   return root.right;
               } else return root.left;
           if (key < root.val) root.left = DeleteNode(root.left, key);
           else root.right = DeleteNode(root.right, key);
           return root;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.