FilesExpand file tree

 main

/

DeleteNodeInBST.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (55 loc) · 1.94 KB

 main

/

DeleteNodeInBST.java

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (55 loc) · 1.94 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class DeleteNodeInBST {

public TreeNode deleteNode(TreeNode root, int key) {

// if root is null then return

if(root == null) return root;

// if key is smaller then delete on left

if(root.val > key){

root.left = deleteNode(root.left , key);

}else if(root.val < key){

root.right = deleteNode(root.right , key);

}

// if we found thenode to be deleted then

else{

// case 1 : if it's left child is null then return right child

if(root.left == null) return root.right;

// case 2 : if it's right child is null then return left child

else if(root.right == null) return root.left;

// case 3 : if both childs are not null then

// set the node to be deleted's value to left most predecessor

// root's right child

root.val = leftPred(root.right);

// and now delete the left most predecessor from root.right sub tree

// here we are deleting coz we know that to delete a

// left most predecessor is easy coz it's left child is always a null

root.right = deleteNode(root.right , root.val);

}

// return the root

return root;

}

public int leftPred(TreeNode root){

// take root's val

int predVal = root.val;

// go to left until its not null

while(root.left != null){

predVal = root.left.val;

root = root.left;

}

// return the value of the predecessor

return predVal;

}

}