I'm trying to write a method to delete a value from within a binary tree. However I'm failing with my logic for the case of deleting a node where it has two children. I'm using the 'replace deleted node with lowest value from the right tree approach', but I'm having problems retaining the correct child node pointers that I want to from the deleted node. Can anybody point me in the right direction with getting this working correctly, and any general suggestions for better code welcomed. Thanks in advance.
Node#delete()
def delete(root, value)
if root == nil
return root
elsif value < root.value
root.left = delete(root.left, value)
elsif value > root.value
root.right = delete(root.right, value)
else root.value == value
puts 'must have found the value'
# case 1 - no children, just delete
if root.left.nil? && root.right.nil?
root = nil
# case 2 - one child, just delete and replace with child
elsif root.left.nil?
root = root.right
elsif root.right.nil?
root = root.left
# case 3 - 2 children, find min value in right subtree and replace with this
else
left_node = root.left
root = min_value(root.right)
root.left = left_node
end
end
return root
end
Contextual code:
Node class:
class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
def self.build_balanced_tree(array)
... (accurately builds a balance binary tree - ommited for brevity)
end
end
Tree class
class Tree
attr_reader :root
def initialize(array)
@root = Node.build_balanced_tree(array)
end
def self.build_balanced_tree(array)
tree = Tree.new(array)
return tree
end
def min_value(root)
current = root
current = current.left until current.left.nil?
return current
end
def nice_print(node, prefix = '', is_left = true)
nice_print(node.right, "#{prefix}#{is_left ? '│ ' : ' '}", false) if node.right
puts "#{prefix}#{is_left ? '└── ' : '┌── ' }#{node.value}"
nice_print(node.left, "#{prefix}#{is_left ? ' ' : '│ '}", true) if node.left
end
end
Script
array = [83, 65, 99, 36, 7, 90, 25, 95, 68, 39, 96, 13, 75, 89, 2]
tree = Tree.build_balanced_tree(array)
tree.nice_print(tree.root)
tree.delete(tree.root, 25)
tree.nice_print(tree.root)
Your delete algorithm assumes that your tree is a binary search tree, but it isn't. And so the algorithm goes to the wrong subtree and doesn't find the value to delete. The build_balanced_tree inserts nodes such that the inorder traversal corresponds to the given array order. So either you must feed it a sorted array, or the values should be inserted one by one according to the BST insertion algorithm.
The case #3 lacks the correct return statement: you should return the right child of the original root (before it got reassigned). So change this code:
left_node = root.left
root = min_value(root.right)
root.left = left_node
to:
min_value(root.right).left = root.left
return root.right
It is not so elegant that the main code has to pass root as argument to many of the methods. I would move those methods to the Node class, and create small wrapper methods on the Tree class that call those methods on the root node. This way the main program does not have to pass that root argument.
With some other small changes, the code could look like this, which uses the BST insertion algorithm (I left out the build_balanced_tree method):
class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
def insert(value)
if value < @value
@left = @left ? @left.insert(value) : Node.new(value)
elsif value > @value
@right = @right ? @right.insert(value) : Node.new(value)
end
return self
end
def delete(value)
if value < @value
@left = @left&.delete(value)
elsif value > @value
@right = @right&.delete(value)
else
puts 'must have found the value'
# case 1 - no children, just delete
return if @left.nil? && @right.nil?
# case 2 - one child, just delete and replace with child
return @right if @left.nil?
return @left if @right.nil?
# case 3 - 2 children, find min value in right subtree and replace with this
@right.min_value().left = @left
return @right
end
return self
end
def min_value()
current = self
current = current.left until current.left.nil?
return current
end
def nice_print(prefix = '', is_left = true)
@right&.nice_print("#{prefix}#{is_left ? '│ ' : ' '}", false)
puts "#{prefix}#{is_left ? '└── ' : '┌── ' }#{@value}"
@left&.nice_print("#{prefix}#{is_left ? ' ' : '│ '}", true)
end
end
class Tree
attr_reader :root
def initialize(array)
@root = nil
array.each { |n| insert(n) }
end
def insert(value)
@root = @root ? @root.insert(value) : Node.new(value)
end
def delete(value)
@root = @root&.delete(value)
end
def nice_print()
@root&.nice_print()
end
end
array = [83, 65, 99, 36, 7, 90, 25, 95, 68, 39, 96, 13, 75, 89, 2]
tree = Tree.new(array)
tree.nice_print()
tree.delete(7)
tree.nice_print()