CodingInterview/deleteNode.cpp at master · ssripadham/CodingInterview · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*        30
    20      40
  10 25   38

          37

       30

    22
  10  25


       30
     /
    10
       \
       25
     22

    if right exists
        bring in left most child of right sub tree
        and delete left most child of right sub tree

     if right does not exist,
        delete the roor node and make left sub tree child of roots parent

  */


  struct node {
     int data;
     struct node * left;
     struct node* right;
     struct node* parent;
  }

  bool isLeaf(struct node* root) {

    return (root->left == NULL && root->right == NULL);
  }


  struct node* getLeftMostChild(struct node* root) {
    //if (root == NULL) return NULL;
    struct node* current = root;
    while (current) {
      current = current->left;
    }

    return current;

  }

  void delete(struct node* root, int data) {

      if (root == NULL) return;

      if (root->data == data) {
          deleteNode(root);
          return;
      }

      if ( data < root->data)
          return delete(root->left, data);
      else
          return delete(root->right, data);

  }


  struct node* deleteNode(struct node* root) {

      if (root == NULL) return;

      if (isLeaf(root)) {
          delete root;
          return;
      }

       //bring in left most child of right sub tree
       // and delete left most child of right sub tree

      if (root->right != NULL) {
          struct node* leftMostChild = getLeftMostChild(root->right);
          root->data = leftMostChild->data;
          delete leftMostChild;
          return root;
      } else {

           // right does not exist,
           //delete the root node and make left sub tree child of roots parent
          root-> parent = root->left;
          root->left->parent = root->parent;
          delete root;
          return root->left;
      }

 }


  }