Binary search tree prints nothing?

Question

I wrote the following Ruby implementation of a basic binary search tree.

I believe that rt = Node.new(data) is not actually modifying the underlying object but is in fact just a temporary variable that is getting discarded.

#!/usr/bin/env ruby

class Node
  attr_accessor :left, :right, :data
  def initialize(d)
    @left = nil
    @right = nil
    @data = d
  end
end

class BST
  attr_accessor :root
  def initialize
    @root = nil
  end

  def add_helper(rt, d)
    if rt != nil
      add_helper(rt.left, d) if d < rt.data
      add_helper(rt.right, d) if d > rt.data
    end
    rt = Node.new(d)
  end

  def add(data)
    add_helper(root, data)
  end

  def print_helper(rt)
    return if rt == nil
    pr(rt.left) if rt.left != nil
    puts rt.data
    pr(rt.right) if rt.right != nil
  end

  def print_tree
    print_helper(root)
  end
end

###########################
b = BST.new
b.add(5)
b.add(-10)
b.print_tree

What is wrong with my implementation? I know that I should debug, and I really have. I put print statements and eventually realized that everything, even the Node object itself, was still nil.

"debugging" can extend a lot farther than simple print statements. Ruby has several debuggers available to you, and, in my group, they get exercised as we ensure our code does what it's supposed to do. Look at [PRY](http://pryrepl.org/), which is both an IRB replacement and a decent debugger, or [debugger](https://github.com/cldwalker/debugger) or [byebug](https://github.com/deivid-rodriguez/byebug), depending on your version of Ruby. See http://stackoverflow.com/a/4127651/128421. — the Tin Man, Oct 28 '13 at 19:16

score 1 · Answer 1 · answered Oct 28 '13 at 19:11

Your instinct is correct: rt = Node.new(d) is creating a new Node object, but it's immediately being discarded.

One way to solve this is by performing the assignment in the parent call, before you've made another recursive call:

def add_helper rt, d
  if rt != nil
    case
    when d < rt.data
      # If rt doesn't have a left child yet, assign it here. Otherwise,
      # recursively descend to the left.
      if rt.left.nil?
        rt.left = Node.new(d)
      else
        add_helper(rt.left, d)
      end
    when d > rt.data
      # Likewise for the right child.
      if rt.right.nil?
        rt.right = Node.new(d)
      else
        add_helper(rt.right, d)
      end
    else
      # Handle duplicate additions however you'd like here.
      raise "Attempt to add duplicate data #{d}!"
    end
  else
    # Now, this can only happen when the root of the entire tree is missing!
    @root = Node.new(d)
  end
end

Another approach that's a little more graceful would be to pass add_helper a block that knows how to add the node if it's missing:

def add_helper rt, d
  if rt.nil?
    # This node isn't assigned yet, so tell our caller to add it.
    yield Node.new(d)
  else
    # Otherwise, perform the appropriate recursive call, passing a block that
    # adds the new node to the correct side of the parent.
    case
    when d < rt.data ; add_helper(rt.left, d) { |n| rt.left = n }
    when d > rt.data ; add_helper(rt.right, d) { |n| rt.right = n }
    else ; raise "Duplicate insertion!"
    end
  end
end

def add data
  # Call add_helper with a block that knows how to assign the root of the whole
  # tree if it's not there:
  add_helper(root, data) { |n| @root = n }
end

Binary search tree prints nothing?

1 Answers1