Traversal of binary tree in ruby

Question

I'm writing a recursive toString method in a binary tree class in Ruby. The algorithm uses two methods as shown below. I have a local variable called result, which is to hold the concatenation of all the values in the tree. For some odd reason, when I concatenate result in the toString algorithm, the root of the tree changes.

def toString
  currentNode = @root
  result = "<"

  if nil != currentNode
    result << (getString currentNode, result)
  end

  result = result + ">"
  return result
end

def getString(currentNode, result)
  if currentNode != nil
    result = currentNode.value.toString

    if nil != currentNode.left
      result << "," # Through debugging, I have noticed that it starts here!!!! 
      result.concat (self.getString currentNode.left, result)
    end

    if nil != currentNode.right
      result << ","
      result.concat (self.getString currentNode.right, result)
    end
  end
  return result
end

So, where I have noted in the comment above, the value at the root of the tree begins to change. Instead of concatenating with result, it concatenates with the root, which changes the tree, instead of simply traversing and concatenating the values. I have used << and concat. Same result. Could someone please help shed some light on this? I am fairly new to Ruby. Thank you. :)

Please add an example of your input and current output and what you expect the output to be. It's difficult to tell from your description what toString is supposed to yield. — mcfinnigan, Jul 24 '14 at 11:37
FYI `to_s` would be a more idiomatic name than `toString` in Ruby. — Andrew Marshall, Jul 24 '14 at 11:39
The tree has nodes and the value of a node could be one of a series of classes, including the tree class itself. i.e. tree inside of a tree. Each of those classes has a to_string — user3286381, Jul 24 '14 at 11:44
In addition to @UriAgassi 's excellent answer which you should accept, you should also note that `getString` ... if the current node is nil... returns `result` which means that `result.concat (self.getString currentNode.left, result)` will effectively double up the string text. `example = "Hello"; example.concat example; p example; => "HelloHello"` — SteveTurczyn, Jul 24 '14 at 12:08

score 1 · Accepted Answer · edited May 23 '17 at 12:28

Contrary to other languages (like java or c#) Strings in ruby are not immutable (by default). This means that if currentNode.value.toString returns the actual string value of the value (and not a copy of it) calling << on it will change the value itself:

class Dummy
  attr_accessor :value
end

dummy = Dummy.new
dummy.value = 'test'

result = dummy.value
result << 'something else'
# => "testsomething else"
dummy.value
# => "testsomething else" # !!!!

To avoid that you need to make sure you return a duplicate of the value, and not the value itself.

dummy.value = 'test'

result = dummy.value.dup
result << 'something else'
# => "testsomething else"
dummy.value
# => "test" # :-)

Traversal of binary tree in ruby

1 Answers1