[Ruby] Binary Search Trees - Hint to delete nodes

Hi everyone,

I’m stuck at the Binary Search Trees assignment, where I need to write a #delete method.

In case the node to delete has children (and these have also children), what would be the strategy to carry out? I can’t even make it out in pseudo-code. I don’t understand how the tree could be rearranged if one node is deleted in this situation. Which child should take its place? What happens to its own children since we can have only two children per node?

Many thanks

First, I want to let you know that I am currently working on updating this lesson, based on suggestions that have been talked about in Discord. But, I have been waiting on hearing back from someone before I submitted the PR. I might just go ahead and submit it, but regardless, here is the details on the lesson update: https://github.com/TheOdinProject/curriculum/issues/17458

As far as deleting a node, this step kinda cooked my noodle. There are multiple scenarios to look at - if the node has no children, if it has one child, if it has two children. For each scenario, determine what needs to be changed. I created several ‘helper methods’ to help me do this step. Plus, I used words like child, parent, grandparent, grandchild to help me make sense of everything that needed to be done. When I was stuck on this step, I was given this link on discord that helped me: https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

Thank you for your support and your advices.
I’ll dig into it again once I’m done with the Rspec section.

@rlmoser99 So I finally looked into this and the link you provided. There’s something odd with the algorithm. I adapted the Python solution from the page to my Ruby code. However, when I tested the #delete behaviour for a leaf (i.e. node without child), it just deleted the whole branch leading to that leaf from the root node.

Now, in my code, it’s because temp is nil when the node is a leaf. So this nil, by recursion, is going back up in the tree as the code wraps up until @root. Leading to the whole branch deletion.

Perhaps it’s something to do with how I build the tree in the first place. Also if I follow the algorithm of your link with a pen and a plain paper, I have the same wrong behaviour as my code.

My Tree class can be viewed here for the record.

I only used that link to learn what needed to happen during the different ‘delete’ scenarios. I didn’t try to adapt the Python solution.

Just looking at your code is hard for me to figure out everything that is going on. If you import your github repo to a repl.it, then I can play around with your code. However, I would try and visualize what is going every step of the recursion, by adding in a puts statement like `puts “Current Node is #{current_node}” or using pry.

It does look like the first half of the delete node is finding the right node, which is one of the next methods to make. So I would take the logic that you are using and put it in a find method. Then in the delete method, you can use the find method.

Also, this could be how you are building the tree… Are you building a balanced BST?

There has been a lot of discussion lately on Discord about this project and so I have found a few more resources that you can check out:

Balanced BST article: https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
Balanced BST video: https://youtu.be/VCTP81Ij-EM
Inserting Node article: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/?ref=lbp
Inserting/Deleting video: https://youtu.be/wcIRPqTR3Kc

In addition, I want to point out that nesting if statements in one method is frowned upon in Ruby. Not that you can’t use that logic, but when you need them, you should create a helper methods. Which also makes me wonder if you have heard about Rubocop? I recently added it to the lesson (and currently submitted another PR to fix the formatting. Check out the info in assignment #7:
https://www.theodinproject.com/courses/ruby-programming/lessons/object-oriented-programming

I think this is the most confusing part for me because in the TOP lesson, Binary Search (the algorithm), working on sorted arrays, is first introduced at 4. and then, BST (the data structure) built from an unsorted array is introduced at 5.

Now, from what you wrote, I understand that Balanced BSTs are BSTs built from a sorted array while there can be BSTs built from unsorted array (and I guess they can’t be balanced?). So I guess I missed that point when doing the lesson.
If that’s accurate, then my tree is not balanced because I built it from an unsorted array. I can rework everything with that in mind and give it another go.

Thanks for the tip. I was not aware of Rubocop and it looks quite handy since I’ve been referring to The Ruby Style Guide from time to time (but not thoroughly enough apparently :sweat_smile:).

We are looking at clarifying this lesson to make sure that students realize that this lesson is about balanced BST, as opposed to just a BST. But yes, balanced BST’s are made from a sorted array, with a certain algorithm to make sure they are built in a balanced way. The previous video link goes into depth about it.

Good luck as you continue working on this project. It is one that most students find difficult. I see a lot of questions about it (on discord).