def assert_equal(x, y)
  raise [x, y].inspect unless x == y
end

class Node
  attr_accessor :left, :right, :value

  def initialize(value)
    @value = value
  end

  def preorder
    [value, self.left&.preorder, self.right&.preorder].flatten.compact
  end
end

class Solution
  # time: O(logn)
  # space: O(n)
  def self.run(node)
    stack = []
    stack.push(node)

    until stack.empty?
      item = stack.pop

      tmp = item.left
      item.left = item.right
      item.right = tmp
      stack.push(item.left) if item.left
      stack.push(item.right) if item.right
    end
  end
end
=begin
       a
     /   \
    b     c
   / \   /
  d   e f

       a
     /   \
    c     b
   /     / \
  f     d   e
=end

root = Node.new('a')
root.left = Node.new('b')
root.right = Node.new('c')
root.left.left = Node.new('d')
root.left.right = Node.new('e')
root.right.left = Node.new('f')
assert_equal(root.preorder, ['a', 'b', 'd', 'e', 'c', 'f'])

Solution.run(root)

assert_equal(root.preorder, ['a', 'c', 'f', 'b', 'e', 'd'])
puts 'Yay!'