Deletion in a Binary Tree | class to create a node with data , left child and right child . ; Inorder traversal of a binary tree ; function to delete the given deepest node ( d_node ) in binary tree ; Do level order traversal until last node ; function to delete element in binary tree ; Do level order traversal to find deepest node ( temp ) and node to be deleted ( key_node ) ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def inorder ( temp ) : NEW_LINE INDENT if ( not temp ) : NEW_LINE INDENT return NEW_LINE DEDENT inorder ( temp . left ) NEW_LINE print ( temp . data , end = " ▁ " ) NEW_LINE inorder ( temp . right ) NEW_LINE DEDENT def deleteDeepest ( root , d_node ) : NEW_LINE INDENT q = [ ] NEW_LINE q . append ( root ) NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT temp = q . pop ( 0 ) NEW_LINE if temp is d_node : NEW_LINE INDENT temp = None NEW_LINE return NEW_LINE DEDENT if temp . right : NEW_LINE INDENT if temp . right is d_node : NEW_LINE INDENT temp . right = None NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT q . append ( temp . right ) NEW_LINE DEDENT DEDENT if temp . left : NEW_LINE INDENT if temp . left is d_node : NEW_LINE INDENT temp . left = None NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT q . append ( temp . left ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def deletion ( root , key ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . left == None and root . right == None : NEW_LINE INDENT if root . key == key : NEW_LINE INDENT return None NEW_LINE DEDENT else : NEW_LINE INDENT return root NEW_LINE DEDENT DEDENT key_node = None NEW_LINE q = [ ] NEW_LINE q . append ( root ) NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT temp = q . pop ( 0 ) NEW_LINE if temp . data == key : NEW_LINE INDENT key_node = temp NEW_LINE DEDENT if temp . left : NEW_LINE INDENT q . append ( temp . left ) NEW_LINE DEDENT if temp . right : NEW_LINE INDENT q . append ( temp . right ) NEW_LINE DEDENT DEDENT if key_node : NEW_LINE INDENT x = temp . data NEW_LINE deleteDeepest ( root , temp ) NEW_LINE key_node . data = x NEW_LINE DEDENT return root NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 11 ) NEW_LINE root . left . left = Node ( 7 ) NEW_LINE root . left . right = Node ( 12 ) NEW_LINE root . right = Node ( 9 ) NEW_LINE root . right . left = Node ( 15 ) NEW_LINE root . right . right = Node ( 8 ) NEW_LINE print ( " The ▁ tree ▁ before ▁ the ▁ deletion : " ) NEW_LINE inorder ( root ) NEW_LINE key = 11 NEW_LINE root = deletion ( root , key ) NEW_LINE print ( ) NEW_LINE print ( " The ▁ tree ▁ after ▁ the ▁ deletion ; " ) NEW_LINE inorder ( root ) NEW_LINE DEDENT