Class: TreeWithNode::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/BinarySearchk/tree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array) ⇒ Tree

Returns a new instance of Tree.



5
6
7
8
 
# File 'lib/BinarySearchk/tree.rb', line 5

def initialize(array)
    @tree = build_tree(array)
    @parent = @tree.value
end

Instance Attribute Details

#parent ⇒ Object

Returns the value of attribute parent.



3
4
5
 
# File 'lib/BinarySearchk/tree.rb', line 3

def parent
  @parent
end

Instance Method Details

#breadth_first_search(target_value) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
 
# File 'lib/BinarySearchk/tree.rb', line 10

def breadth_first_search(target_value)
    queue = [@tree]
    until queue.empty?
        current_node = queue.shift
        return "Found #{current_node.value}" if current_node.value == target_value
        queue.push current_node.left unless current_node.left.nil?
        queue.push current_node.right unless current_node.right.nil?
    end
    nil
end

#depth_first_search(target_value) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
 
# File 'lib/BinarySearchk/tree.rb', line 21

def depth_first_search(target_value)
    stack = [@tree]
    until stack.empty?
        current_node = stack.pop
        return "Found #{current_node.value}" if current_node.value == target_value
        stack.push current_node.right unless current_node.right.nil?
        stack.push current_node.left unless current_node.left.nil?
    end
    nil
end

#dfs_rec(target_value, node = @tree) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
 
# File 'lib/BinarySearchk/tree.rb', line 32

def dfs_rec(target_value, node = @tree)
    if node.nil?
        return nil
    else
        return "Found #{node.value}" if node.value == target_value
        search_left_child = dfs_rec(target_value, node.left)
        search_right_child = dfs_rec(target_value, node.right)
    end
    return (search_right_child or search_left_child)
end