CODEWITHSUNDEEP
rubybinary-search-tree
Thermatix
Thermatix

Reputation: 2929

I'm implementing a Binary Search tree in ruby but I'm having an issue with getting a node's parent

Due to the way the tree is initialized, any node is aware of it's children but not it's parent.

How can I find the parent without passing it in, or is that the only way? Unless there's a way to automatically pass a reference to the parent in?

At the moment I create a tree like so:

Node[
    5,
    Node[
        2,
        nil,
        Node[
            3
        ]
    ],
    Node[
        9,
        node[
            7
        ]
    ]
]

Upvotes: 0

Views: 230

Answers (1)

Stefan
Stefan

Reputation: 114178

It is definitely possible. You can set the parent when assigning left or right:

class Node
  attr_accessor :key, :parent
  attr_reader :left, :right

  def self.[](key, left = nil, right = nil)
    new(key, left, right)
  end

  def initialize(key, left, right)
    @key = key
    self.left = left
    self.right = right
  end

  def left=(node)
    node.parent = self if node
    @left = node
  end

  def right=(node)
    node.parent = self if node
    @right = node
  end
end

Example:

root = Node[
         5,
         Node[
             2,
             nil,
             Node[
                 3
             ]
         ],
         Node[
             9,
             Node[
                 7
             ]
         ]
       ]

root.key #=> 5
root.left.key # => 2
root.left.parent.key #=> 5
root.left.parent == root #=> true

Upvotes: 1

Related Questions