Iam_Sandeep

Delete a node in BST

Apr 12th, 2022
693
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.02 KB | None | 0 0
  1. class Solution:
  2.     def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
  3.         def getMin(x):
  4.             while x.left:
  5.                 x=x.left
  6.             return x.val
  7.            
  8.         def delete(root,key):
  9.             if not root:return None
  10.             if root.val<key:
  11.                 root.right=delete(root.right,key)
  12.             elif root.val>key:
  13.                 root.left=delete(root.left,key)
  14.             else:
  15.                 #if it lead
  16.                 if not root.left and not root.right:
  17.                     root=None
  18.                 #if it has one child
  19.                 elif not root.left:
  20.                     root=root.right
  21.                 elif not root.right:
  22.                     root=root.left
  23.                 #if it has two children
  24.                 else:
  25.                     swap=getMin(root.right)
  26.                     root.val=swap
  27.                     root.right=delete(root.right,swap)
  28.             return root
  29.         return delete(root,key)
  30.                    
Advertisement
Add Comment
Please, Sign In to add comment