private static < T extends Comparable < ? super T > > TreeNode < T > deleteNode ( TreeNode < T > root ) { if ( root . left == null && root . right == null ) return null ; if ( root . left == null ) { // If the left child is empty, then the right subtree can consist of at most // one node, otherwise it would have been unbalanced. So, just return // the right child. return root . right ; } else { TreeNode < T > node = root . left ; Stack < TreeNode < T > > stack = new Stack <> ( ) ; while ( node . right != null ) { stack . push ( node ) ; node = node . right ; } if ( ! stack . isEmpty ( ) ) { stack . peek ( ) . right = node . left ; node . left = root . left ; } node . right = root . right ; TreeNode < T > newRoot = node ; while ( ! stack . isEmpty ( ) ) { node = stack . pop ( ) ; if ( ! stack . isEmpty ( ) ) stack . peek ( ) . right = newRoot . assimilateOverlappingIntervals ( node ) ; else newRoot . left = newRoot . assimilateOverlappingIntervals ( node ) ; } return newRoot . balanceOut ( ) ; } }
Deletes a node from the tree . The caller of this method needs to check if the node is actually empty because this method only performs the deletion .