Over a million developers have joined DZone.

# Binary Search Tree – Programming Praxis solution

·

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Earlier this year I was influenced by two things that got me to re-think what I work on in my free time. The first was this podcast from Software Engineering Radio with “Uncle Bob” Bob Martin on software craftsmanship. The second was a blog on the value of fundamentals in software development. As a result I am now focusing on incorporating puzzles as well as learning new languages or frameworks . This entry is a solution to the Binary Search Tree problem from Programming Praxis. While this post does not aim to be a thorough explanation of how a binary search tree works, I will present my code and briefly explain it.

The problem asked you to implement search, insert delete and enlist ( I took enlist to mean generate a list of values from the tree in order). Since I use Java on the day job, and I want to get better in other languages, I implemented my solution in Ruby. Here are the public methods that fufill the requirements of the problem.

```require 'node'

module Trees
class BinarySearchTree

def initialize(root = nil)
@root = root
end

def search(value)
search_for_node(@root,Node.new(value))
end

def insert(value)
@root = insert_value(@root,value)
end

def delete(value)
@root = delete_node(@root,Node.new(value))
end

def in_order_list
vals = []
inorder(vals,@root)
vals
end```

These methods just delegate to private methods that actually do the work. Let’s consider search and insert first.

```private

def search_for_node(tnode,node)
if tnode.nil?
return nil
end

if tnode == node
tnode = node
elsif node < tnode
tnode = search_for_node(tnode.left,node)
else
tnode = search_for_node(tnode.right,node)
end
tnode
end

def insert_value(tnode,value)
if tnode.nil?
tnode = Node.new(value)
elsif value < tnode.value
tnode.left = insert_value(tnode.left,value)
elsif value > tnode.value
tnode.right = insert_value(tnode.right,value)
elsif value == tnode.value
tnode.value = value
end
tnode
end```

Search and insert work almost identically. With search you keep traversing the tree until you find your value, or return nil when you have exhausted your options. With insert you actually want to keep going until you find a nil node, then you know thats where to insert. One thing I did in my insert method was that if you supply a value that already exists in the tree I simply update the node with that value. I’m sure there are better ways of handling that situation, but I felt simply updating with an existing value causes no harm. Now, deleting is not quite so straight forward, although still not that difficult.

```def delete_node(tnode,node)
if tnode == node
tnode = remove(tnode)
elsif node < tnode
tnode.left = delete_node(tnode.left,node)
else
tnode.right = delete_node(tnode.right,node)
end
tnode
end

def remove(node)
if node.left.nil? && node.right.nil?
node = nil
elsif !node.left.nil? && node.right.nil?
node = node.left
elsif node.left.nil? && !node.right.nil?
node = node.right
else
node = replace_parent(node)
end
node
end```

When deleting a node from the tree there are 4 cases to consider:

1. The node has no children
2. The node has a left child only
3. The node has a right child only
4. The node has both a right and left child

The first three are pretty straight forward to handle. With no children, obviously the node to be deleted is just set to null. If the node only has one child you merely set the reference of the node to be deleted to that of it's child. The situation of 0-1 child nodes is handled by the first three branches of the if-else statements in the remove method. The following methods are used to handle the case of a node with 2 children.

```def replace_parent(node)
node.value = successor_value(node.right)
node.right = update(node.right)
node
end

def successor_value(node)
unless node.left.nil?
successor_value(node.left)
end
node.value
end

def update(node)
unless node.left.nil?
node.left = update(node)
end
node.right
end
```

Deleting a node with 2 children is handled in two steps. First you update the value of the node to be deleted with the value of the node's in-order successor or predecessor. Then the duplicate node needs to be deleted and handle the case if it has a child node. It is worth noting due to the properties of binary trees, an in-order successor or predecessor will only ever have a right or left child.
For me it seemed more natural to use the in-order successor. The replace_parent method first updates the value of the node to be deleted with the value returned from the successor_value method. Then duplicate node is then removed and the right child of the newly updated node is set to the right child of the in-order successor or null. This last part is handled by the update method. Here is the code to get a list of the values from the tree in ascending order

```def inorder(list, node)
unless node.nil?
inorder(list, node.left)
list.push(node.value)
inorder(list, node.right)
end
end
```

Finally here is the code for the Node class:

```module Trees
class Node
include Comparable
attr_accessor :left,:right,:value

def initialize(value = nill, left = nil, right = nil)
@value = value
@left = left
@right = right
end

def <=>(otherNode)
@value <=> otherNode.value
end

def to_s
"[value: #{@value} left=> #{@left} right=> #{@right}]"
end
end
end
```

Topics:

Published at DZone with permission of Bill Bejeck , DZone MVB .

Opinions expressed by DZone contributors are their own.