package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) { // Inorder flatten
	prev := (*TreeNode)(nil)
	flattenHelper(root, &prev)
}

// Reverse order of the inorder traversal
// root -> left -> right => right -> left -> root
func flattenHelper(root *TreeNode, prev **TreeNode) {
	if root == nil {
		return
	}
	flattenHelper(root.Right, prev)
	flattenHelper(root.Left, prev)
	root.Left = nil
	root.Right = *prev
	*prev = root
}

// func main() {
// 	root1 := sortedArrayToBST([]int{3, 2, 4, 1, 6, 5, 7})
// 	printTree(root1)
// 	flatten(root1)
// 	printTree(root1)
// }