Poly Tree Node
I wrote my own Poly Tree Node Class.
class PolyTreeNode attr_reader :children, :parent, :value def initialize(value) @value = value @parent = nil @children = [] end
def parent=(parent) @parent.children.delete(self) if @parent @parent = parent unless parent == nil || parent.children.include?(self) parent.children << self end end
Since a tree node points to its parent and to its children, I need to take care of both pointers when a new parent is assigned. Since this node’s parent will point to it, I need to remove it from its parent’s children.
def add_child(child) child.parent = self end
def remove_child(child) raise "That is not my child!" unless @children.include?(child) child.parent = nil end
Likewise, when a child is added to a node, I need to add pointers to both objects. When adding a child, I need to set this node to be that child’s parent, and the #parent= method that’s already been defined will take care of adding the child to this nodes list of children.
A little bit of magic happens with remove child. When child.parent is assigned to nil that will remove the two objects pointers to each other. When an object has no pointers to it, it gets “garbage collected” and no longer exists. In programming, if nobody knows about you, there’s no reason for you to exist.
def dfs(target_value) return self if @value == target_value return nil if @children.empty? result_node = nil @children.each do |child| result_node = child.dfs(target_value) break if result_node end result_node end
This is depth first search. It recursively searches each child it sees. That means that it will get to a return statement before it actually returns a value from the call stack.
def bfs(target_value) queue = [self] until queue.empty? node = queue.shift return node if node.value == target_value node.children.each {|child| queue << child } end nil end
This is breadth first search. It checks each node of the tree by adding a node’s children to the queue as it checks them.
def inspect @value.inspect end end
Inspect is in there for debugging. It’s really useful to define an inspect method because this is what irb and pry call to display ruby return values. Rather than see all of the information for the object (which includes a bunch of long hashes), it’s much easier to display each node as just it’s value. You could define inspect to serve whatever debugging purpose you need at the time though.