class Solution(object): def insert(self,root,node): """ :type root: TreeNode :type node: TreeNode :rtype: TreeNode """ # a util function to inser a given "node" in to a tree rooted at root # a node must not already exist in tree! if root is None: # if tree is empty, return node being insert return node elif node is None: # if node being inserted is None, return root return root else: # find proper node's position in tree p = None cur = root while cur: p = cur if node.val <= cur.val: cur = cur.left else: cur = cur.right # p is going to be father of node! # find if its suited as left or right child if node.val <= p.val: p.left = node else: p.right = node return root # modified tree returned def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ if root: # a loop to find a node with a given key p = None cur = root while cur and cur.val != key: p = cur if cur.val < key : # if key to be removed is larger than current's key # then key to be removed is in right subtree cur = cur.right else: # if key to be removed in smaller than current's key # then key to be removed is in left subtree cur = cur.left # at this point p points to a parent of a node to be removed! # cur is node to be removed! if cur is None: # key is absent in the tree, nothing to do! return root if p is None: # root is being removed! left = root.left # left child root = root.right # right child always inherits the role of root root = self.insert(root,left) # insert left in new root else: # detach both left and right children left = cur.left right = cur.right cur.left = cur.right = None # insert left into right right = self.insert(right,left) # right child inherits father's role if p.left is cur: p.left = right else: p.right = right return root
Simple nonrecursive python solution with comments to explain algorithm
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.