ruby - Stoping condition of recursive method doesn't work at the right time -

a peculiar problem ocurring me. i'm coding binary search tree methods:

class binarysearchtree   class node     attr_accessor :value, :height     attr_accessor :left, :right      def initialize(value, height)       @value = value       @height = height     end   end   attr_accessor :root  def initialize   @root = node.new(nil, 0) end  def insert(value)   node = @root   loop     case value <=> node.value     when -1       if node.left.nil?         node.left = node.new(value, node.height + 1)         break       else         node = node.left       end     when 1       if node.right.nil?         node.right = node.new(value, node.height + 1)         break       else         node = node.right       end     else       node.value = value       break     end   end end  def delete(value, node = @root)   return if node.nil?   if value == node.value     node = delete_node(node)   elsif value < node.value     node.left = delete(value, node.left)   elsif     node.right = delete(value, node.right)   end   node end  def delete_node(node)   if node.left.nil? && node.right.nil?     node = nil   elsif node.left.nil? || node.right.nil?     if node.left.nil?       node = node.right       update_subtrees_height(node, -1, {left: false, right: true})     else       node = node.right end       update_subtrees_height(node, -1, {left: true, right: false})   else     #todo   end   node end  def update_subtrees_height(node, value, options = {left: true, right: true})   return if node.nil?   node.height = node.height + value   update_subtrees_height(node.left, value, options) if options[:left]   update_subtrees_height(node.right, value, options) if options[:right] end  # debug def print_tree(node = @root)   return if node.nil?   puts "#{node.left.nil? ? 'null' : node.left.value} - #{node.nil? ? 'null' : node.value}(h#{node.height}) - #{node.right.nil? ? 'null' : node.right.value}"   print_tree(node.left)   print_tree(node.right) end end 

the problem occurs in update_subtrees_height. consider test:

btree = binarysearchtree.new  [8,7,9,10].each |v|   btree.insert(v) end  btree.print_tree btree.root btree.root = btree.delete(9) btree.print_tree btree.root 

step step, test does:

1) buil tree , print (the output print_tree method):

7 - 8(h0) - 9 null - 7(h1) - null null - 9(h1) - 10 null - 10(h2) - null 

that represents following tree:

   8     # height 0   / \  7   9   # height 1       \       10 # height 2 

2) delete 9 tree , print again:

7 - 8(h0) - 10 null - 7(h1) - null null - 10(h0) - null 

as showed in output, height of child 10 (represented h in output) 0, when should 1. hapens why when call recursive method update_subtrees_height, it's called 2 times before stop. removing 9 replace right child, 10, , call update_subtrees_height passing node 10 decrease height.

calling update method, i've stoping condition return if node.nil?. node 10, doesn't stop @ first iteration, decreaing height 1 (the desired result) , call method recursivly, passing node.right. node.right nil, method doesn't stop @ next iteration (!), decreasing height of node 10 again (to 0 time, output had). @ third iteration, method stop.

someone have idea why third iteration happens?

there error in delete_node method:

def delete_node(node)   if node.left.nil? && node.right.nil?     node = nil   elsif node.left.nil? || node.right.nil?     if node.left.nil?       node = node.right       update_subtrees_height(node, -1, {left: false, right: true})     else       node = node.right end  #                     ^^^       update_subtrees_height(node, -1, {left: true, right: false})   else     #todo   end   node end 

fix following , work!

def delete_node(node)   if node.left.nil? && node.right.nil?     node = nil   elsif node.left.nil? || node.right.nil?     if node.left.nil?       node = node.right       update_subtrees_height(node, -1, {left: false, right: true})     else       node = node.right       update_subtrees_height(node, -1, {left: true, right: false})     end   else     #todo   end   node end