# Binary Tree

**URL:** <https://www.ruby-forum.com/t/binary-tree/92590>\
**Category:** Ruby\
**Created:** [April 21, 2007, 4:28am UTC](https://www.ruby-forum.com/t/binary-tree/92590 "2007-04-21T04:28:39Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 4:28am UTC](https://www.ruby-forum.com/t/binary-tree/92590/1 "2007-04-21T04:28:39Z")

</div>

Hi all!

I’m a newbie in Ruby and I am trying to implement a Binary Tree.  
However, it doesn’t work. Could someone please help me?

Thank you !

class Node  
attr\_accessor :left, :right, :key, :data

def initialize(key, data)  
@left = nil  
@right = nil  
@key = key  
@data = data  
end

def to\_s()  
print "Key = ", @key, " Data = ", @data  
end  
end

class Tree  
attr\_accessor :root

public  
def initialize()  
@root = nil  
print "Root Object Id ", @root.object\_id, “\n”  
end

def insert(newNode)  
insertNode(@root, newNode)  
end

def visit()  
visitNode(@root)  
end

private  
def insertNode(node, newNode)  
print "Node Object Id ", node.object\_id, “\n”  
print "New Node Object Id ", newNode.object\_id, “\n”  
if (node == nil)  
node = newNode  
print "Node Affected Object Id ", node.object\_id, “\n”  
print @root  
print node  
else  
if (newNode.data \<= node.data)  
insertNode(node.left, newNode)  
print “Gauche”  
else  
insertNode(node.right, newNode)  
print “Droite”  
end  
end  
end

def visitNode(node)  
if (node != nil)  
print node.key

```
  if (node.left != nil)
    visitNode(node.left)
  end

  if (node.right != nil)
    visitNode(node.right )
  end
end

```

end  
end

arbre = Tree.new  
arbre.insert(Node.new(1, “un”))  
arbre.insert(Node.new(2, “deux”))  
arbre.insert(Node.new(3, “trois”))

arbre.visit()

---

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 6:26am UTC](https://www.ruby-forum.com/t/binary-tree/92590/2 "2007-04-21T06:26:33Z")

</div>

Martin wrote:

> def initialize(key, data)
> 
> ```
> insertNode(@root, newNode)
> if (node == nil)
> print "Droite"
> end
> 
> ```
> 
> arbre.insert(Node.new(1, “un”))  
> arbre.insert(Node.new(2, “deux”))  
> arbre.insert(Node.new(3, “trois”))
> 
> arbre.visit()

Martin,

In short, I don’t know how to fix it. But the problem is with this line:

node = newNode

It doesn’t seem to do what you want. I think it takes the reference  
variable “node” (previously pointing at @root, until the method  
recurses) and point it at a new variable (“newNode”). That isn’t what  
you want–you want to replace the contents of the node, not change the  
reference. I don’t know how to do this. I got something by changing the  
above line to “@root = newNode”, but that really breaks the algorithm.

Dan Z.

---

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 6:35am UTC](https://www.ruby-forum.com/t/binary-tree/92590/3 "2007-04-21T06:35:33Z")

</div>

On Apr 21, 12:26 am, Dan Z. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > end  
> > def insert(newNode)  
> > print "New Node Object Id ", newNode.object\_id, “\n”  
> > insertNode(node.right, newNode)  
> > visitNode(node.left)  
> > arbre.insert(Node.new(1, “un”))
> 
> It doesn’t seem to do what you want. I think it takes the reference  
> variable “node” (previously pointing at @root, until the method  
> recurses) and point it at a new variable (“newNode”). That isn’t what  
> you want–you want to replace the contents of the node, not change the  
> reference. I don’t know how to do this. I got something by changing the  
> above line to “@root = newNode”, but that really breaks the algorithm.
> 
> Dan Z.

Hi Dan,

You’re right, the problematic line is definitely: node = newNode.

When the tree has no root (@root == nil), the first node added to the  
tree should become the root. That’s why I check just before if the  
node is nil. Since this method is called by insert which pass to  
insertNode the class attribute @root, why Ruby doesn’t change the  
value of @root for the value of newNode. I thought that Ruby was using  
only references… Am I right?

Thank you for your help…

Martin

---

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 8:42am UTC](https://www.ruby-forum.com/t/binary-tree/92590/4 "2007-04-21T08:42:39Z")

</div>

removed\_email\_address@domain.invalid wrote:

> > > ```
> > > @right = nil
> > > 
> > > ```
> > > 
> > > def initialize()  
> > > def insertNode(node, newNode)  
> > > print “Gauche”  
> > > visitNode(node.left)  
> > > arbre.insert(Node.new(3, “trois”))  
> > > you want–you want to replace the contents of the node, not change the  
> > > tree should become the root. That’s why I check just before if the

Ruby doesn’t change the value of @root (even though that is what is  
pointed to by “node”) because it’s busy changing the value of “node”.  
Ruby variables don’t seem to mate for life. As soon as ruby sees the  
‘=’, “node” no longer points at @root. This may be one disadvantage of a  
really loosely typed language. As for how to make the binary tree work,  
I can’t think of a way that doesn’t involve rewriting a lot of it to  
avoid this problem. If you really wanted to, perhaps you could store the  
nodes in an array and pass around index numbers instead of passing  
around nodes themselves? But then you lose some of advantages of a  
binary tree, and it’s really not elegant.

You could rewrite the algorithm a little, but it is going to involve two  
things:

- at some point, you will need to explicitly set @root
- I suspect “node.left =” and “node.right =” will work as expected, so  
you wan assign to those directly, even if “node” is just some variable.

Sorry for not having a good answer,

Dan

---

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 2:06pm UTC](https://www.ruby-forum.com/t/binary-tree/92590/5 "2007-04-21T14:06:05Z")

</div>

Martin wrote:

> I’m a newbie in Ruby and I am trying to implement a Binary Tree.  
>   
> def to\_s()  
> print "Key = ", @key, " Data = ", @data  
> end  
> end  
> btw: The method to\_s should _return_ a string _not print_ a string!

def to\_s  
“Key = #@key Data = #@data”  
end

regards  
Jan

---

<div class="post-metadata">

**Author:** ![martin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/73ab20/32.png) [@martin](https://www.ruby-forum.com/u/martin)\
**Post date:** [April 21, 2007, 8:55am UTC](https://www.ruby-forum.com/t/binary-tree/92590/6 "2007-04-21T08:55:39Z")

</div>

I think this is more complex than necessary. I’ll go through yours  
and then show you another approach. Your tree is a little weird,  
though, as it doesn’t sort or balance anything. That’s not wrong,  
just unusual.

On Sat, Apr 21, 2007 at 11:28:41AM +0900, Martin wrote:

> class Node  
> attr\_accessor :left, :right, :key, :data
> 
> def initialize(key, data)

Best to provide a default for key and data. E.g.,

def initialize(key=“root”, data=0)

> ```
> @left = nil
> @right = nil
> @key = key
> @data = data
> 
> ```
> 
> end
> 
> def to\_s()  
> print "Key = ", @key, " Data = ", @data

More idiomatic ruby:

p “Key = #{@key} Data = #{@data}”

> end  
> end
> 
> class Tree

The Tree class isn’t really helpful here. Having a higher level  
object to contain the nodes isn’t bad or wrong, but it complicates  
things and it’s distracting. My implementation below just omitted  
this, but you could put it back. Putting the logic in the Tree class  
is actually probably better, since individual Node instances could  
be part of multiple Trees with different logic all at the same time,  
but we’re getting ahead of ourselves.

> private  
> def insertNode(node, newNode)  
> print "Node Object Id ", node.object\_id, “\n”  
> print "New Node Object Id ", newNode.object\_id, “\n”  
> if (node == nil)  
> node = newNode

The variable ‘node’ is an argument variable. It’s basically like a  
stack variable in C. When insertNode returns, the binding goes away  
and so this assignment only does something within the context of this  
function. The variable “node” doesn’t hold a reference to the original  
variable’s slot from the calling function. Here’s another example:

def foo()  
x = 1  
bar(x)  
p x  
end

def bar(y)  
y = 5  
p y  
end

foo()  
5  
1

See? When bar is done, the ‘y’ variable goes away and the value ‘5’ is  
lost. It’s not stored in the place the original ‘x’ lived because they  
are different variables.

> ```
> end
> 
> ```
> 
> arbre.insert(Node.new(2, “deux”))  
> arbre.insert(Node.new(3, “trois”))
> 
> arbre.visit()

Ok, here’s mine:

class Node  
attr\_accessor :left, :right, :key, :data

def initialize(key=“root”, data=0)  
@left = nil  
@right = nil  
@key = key  
@data = data  
end

def insert(newNode)  
return if nil == newNode

# insert it to the left if it’s \<= what we have, otherwise right

if self.data \<= newNode.data then  
if @left then  
@left.insert newNode  
else  
@left = newNode  
end  
else  
if @right then  
@right.insert newNode  
else  
@right = newNode  
end  
end  
end

def visit(depth=0)  
print " " \* depth \* 2 # two spaces per level in the tree  
print “#{self.key} -\> #{self.data}\n”  
@left.visit(depth+1) if @left  
@right.visit(depth+1) if @right  
end  
end

arbre = Node.new  
arbre.insert Node.new(“un”, 1)  
arbre.insert Node.new(“quatre”, -4)  
arbre.insert Node.new(“deux”, 2)  
arbre.insert Node.new(“trois”, 3)

arbre.visit

ciao,

–nash