Class: BinaryTree

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures/binary_tree.rb

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ BinaryTree

Returns a new instance of BinaryTree.



24
25
26
27
 
# File 'lib/data_structures/binary_tree.rb', line 24

def initialize
  @head = nil
  @leaves = []
end

Class Method Details

.from_array(array) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/data_structures/binary_tree.rb', line 2

def self.from_array(array)
  binary_tree = BinaryTree.new
  return binary_tree if array.empty?

  head_node = BinaryTreeNode.new(array.first)
  binary_tree.send(:head=, head_node)
  return binary_tree if array.length == 1

  current_node = head_node
  node_arr = []
  array[1..-1].each do |el|
    node = BinaryTreeNode.new(el, current_node)
    node_arr << node
    binary_tree.send(:leaves) << node
    current_node.send(:left_child).nil? ? current_node.send(:left_child=, node) : current_node.send(:right_child=, node)
    binary_tree.send(:leaves).delete(current_node)
    current_node = node_arr.shift if current_node.send(:right_child)
  end

  binary_tree
end

Instance Method Details

#breadth_first_search(target = nil, &prc) ⇒ Object

Raises:

  • (ArgumentError) 


47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/data_structures/binary_tree.rb', line 47

def breadth_first_search(target=nil, &prc)
  raise ArgumentError.new('Must pass either a target value or a block') unless (target || prc) && !(target && prc)
  prc ||= Proc.new { |node| node.send(:val) == target }

  nodes = [@head]
  until nodes.empty?
    node = nodes.shift
    next if node.nil?
    return node if prc.call(node)
    nodes.concat([node.send(:left_child), node.send(:right_child)])
  end

  nil
end

#depth_first_search(target = nil, start_node = nil, &prc) ⇒ Object

Raises:

  • (ArgumentError) 


29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/data_structures/binary_tree.rb', line 29

def depth_first_search(target=nil, start_node=nil, &prc)
  raise ArgumentError.new('Must pass either a target value or a block') unless (target || prc) && !(target && prc)
  prc ||= Proc.new { |node| node.send(:val) == target }

  return nil if @head.nil?
  start_node ||= @head

  return start_node if prc.call(start_node)

  [start_node.send(:left_child), start_node.send(:right_child)].each do |child|
    next if child.nil?
    result = depth_first_search(nil, child, &prc)
    return result unless result.nil?
  end

  nil
end