BST tree deleting the max via /r/learnprogramming

BST tree deleting the max

Some of the code below seems too obvious, traversing the tree using its right most branch since that is where all the max values are.However, I don't understand a few things about this code I saw in Robert Sedgewick's Algorithms book.

 public void deleteMax() { if (isEmpty()) throw new NoSuchElementException(""); root = deleteMax(root); assert check(); } private Node deleteMax(Node x) { if (x.right == null) return x.left; x.right = deleteMax(x.right); x.size = size(x.left) + size(x.right) + 1; return x; } 

In the private method why do we return the left element if the right child of x is null ?From my understanding x would be the maximum if x has no right children and is the right most node we could go to.Also I don't understand when do we return x in the last line of the 2nd method.

Submitted July 09, 2017 at 04:49PM by SamCryBaby202
via reddit


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s