package main;

import (
	"os"
	"fmt"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func (tn *TreeNode) Dump() string {
	l := "nil"
	if tn.Left != nil { l = tn.Left.Dump()}
	r := "nil"
	if tn.Right != nil { r = tn.Right.Dump()}
	return fmt.Sprintf("TreeNode(%v, %s, %s)", tn.Val, l, r)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
	var vals []int

	var getVals func(r *TreeNode) []int
	getVals = func(r *TreeNode) []int {
		if r == nil { return []int{} }
		var vs []int = []int{ r.Val }
		vs = append(vs, getVals(r.Left)[:]...)
		vs = append(vs, getVals(r.Right)[:]...)
		return vs
	}

	vals = getVals(root)
	for {
		var changed bool = false
		for i := range (len(vals)-1) {
			if vals[i] > vals[i+1] {
				vals[i+1], vals[i] = vals[i], vals[i+1]
				changed = true
			}
		}
		if changed == false { break }
	}

	var ret TreeNode

	var tail *TreeNode = &ret

	for i, v := range vals {
		tail.Val = v
		if i < (len(vals) - 1) { tail.Right = &(TreeNode {}) }
		tail = tail.Right
	}

	return &ret
}

func main() {
	r := TreeNode { 5, &(TreeNode {1, nil, nil}), &(TreeNode {7, nil, nil})}
	t := increasingBST(&r)
	fmt.Println(r.Dump())
	fmt.Println(t.Dump())
	os.Exit(0)
}