1def assert_equal(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5class Node
 6  attr_accessor :left, :right, :value
 7
 8  def initialize(value)
 9    @value = value
10  end
11
12  def preorder
13    [value, self.left&.preorder, self.right&.preorder].flatten.compact
14  end
15end
16
17class Solution
18  # time: O(logn)
19  # space: O(n)
20  def self.run(node)
21    stack = []
22    stack.push(node)
23
24    until stack.empty?
25      item = stack.pop
26
27      tmp = item.left
28      item.left = item.right
29      item.right = tmp
30      stack.push(item.left) if item.left
31      stack.push(item.right) if item.right
32    end
33  end
34end
35=begin
36       a
37     /   \
38    b     c
39   / \   /
40  d   e f
41
42       a
43     /   \
44    c     b
45   /     / \
46  f     d   e
47=end
48
49root = Node.new('a')
50root.left = Node.new('b')
51root.right = Node.new('c')
52root.left.left = Node.new('d')
53root.left.right = Node.new('e')
54root.right.left = Node.new('f')
55assert_equal(root.preorder, ['a', 'b', 'd', 'e', 'c', 'f'])
56
57Solution.run(root)
58
59assert_equal(root.preorder, ['a', 'c', 'f', 'b', 'e', 'd'])
60puts 'Yay!'