Class: DSA::BinarySearchTree

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/binary_search_tree.rb

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



5
6
7
8
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 5

def initialize
  @root = nil
  @size = 0
end

Instance Method Details

#delete(val) ⇒ Object 



20
21
22
23
24
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 20

def delete(val)
  @root, deleted = delete_recursive(@root, val)
  @size -= 1 if deleted
  deleted
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


61
62
63
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 61

def empty?
  @size == 0
end

#inorder ⇒ Object 



36
37
38
39
40
41
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 36

def inorder
  return [] if empty?
  result = []
  traverse_inorder(@root, result)
  result
end

#insert(val) ⇒ Object 



10
11
12
13
14
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 10

def insert(val)
  @root, added = insert_recursive(@root, val)
  @size += 1 if added
  self
end

#max ⇒ Object

Raises:

  • (IndexError) 


31
32
33
34
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 31

def max
  raise IndexError, "tree is empty" if empty?
  find_max(@root).val
end

#min ⇒ Object

Raises:

  • (IndexError) 


26
27
28
29
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 26

def min
  raise IndexError, "tree is empty" if empty?
  find_min(@root).val
end

#postorder ⇒ Object 



50
51
52
53
54
55
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 50

def postorder
  return [] if empty?
  result = []
  traverse_postorder(@root, result)
  result
end

#preorder ⇒ Object 



43
44
45
46
47
48
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 43

def preorder
  return [] if empty?
  result = []
  traverse_preorder(@root, result)
  result
end

#search(val) ⇒ Object 



16
17
18
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 16

def search(val)
  !!find_node(@root, val)
end

#size ⇒ Object 



57
58
59
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 57

def size
  @size
end

#to_a ⇒ Object 



65
66
67
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 65

def to_a
  inorder
end