algorithms_in_ruby/binary_tree.rb at master · saadbinakhlaq/algorithms_in_ruby · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Node
  attr_accessor :value,
                :left,
                :right

  def initialize(value)
    @value = value
    @left  = nil
    @right = nil
  end
end

class BinaryTree
  attr_reader :root

  def initialize
    @root = nil
  end

  def insert(value)
    if @root == nil
      @root = Node.new(value)
    else
      temp = @root
      node = Node.new(value)

      while temp != nil
        if value < temp.value
          if temp.left.nil?
            temp.left = node
            break
          else
            temp = temp.left
          end
        else
          if temp.right.nil?
            temp.right = node
            break
          else
            temp = temp.right
          end
        end
      end
    end
    @root
  end

  def in_order
    in_order_traversal(@root)
  end

  def post_order
    post_order_traversal(@root)
  end

  def pre_order
    pre_order_traversal(@root)
  end

  def levelwise
    queue = []
    dummy = nil
    level = 0
    temp  = root
    queue << temp
    queue << dummy
    puts "level: #{level}"

    loop do
      temp = queue.shift

      if temp == dummy
        if !queue.empty?
          level += 1
          puts "level #{level}"
          queue.push(dummy)
        end
      else
        puts "value #{temp.value}"
        if !temp.left.nil?
          queue.push(temp.left)
        end

        if !temp.right.nil?
          queue.push(temp.right)
        end
      end

      break if queue.empty?
    end
  end

  private

  def in_order_traversal(root)
    temp = root

    if !temp.nil?
      in_order_traversal(temp.left)
      puts temp.value
      in_order_traversal(temp.right)
    end

    nil
  end

  def post_order_traversal(root)
    temp = root

    if !temp.nil?
      post_order_traversal(temp.left)
      post_order_traversal(temp.right)
      puts temp.value
    end

    nil
  end

  def pre_order_traversal(root)
    temp = root

    if !temp.nil?
      puts temp.value
      pre_order_traversal(temp.left)
      pre_order_traversal(temp.right)
    end

    nil
  end
end