Bill Bejeck is a software developer and enjoys the challenges that software development brings. Bill also loves exploring new languages, technologies and learning and educating by blogging. Bill is a DZone MVB and is not an employee of DZone and has posted 29 posts at DZone. You can read more from them at their website. View Full User Profile

Binary Search Tree – Programming Praxis solution

09.14.2011
| 9497 views |
  • submit to reddit

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
    attr_reader :root

    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


References
Published at DZone with permission of Bill Bejeck, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)