// 첫 번째 시도 : 사이클 발생 (tail = tail.right에서 , tail에 left가 포함되어 할당되기 떄문)
// 다른 풀이 참고 : tail.left = null로

var increasingBST = function (root) {
  let newRoot = new TreeNode(0);
  let tail = newRoot;

  const traverse = (cur) => {
    if (!cur) return;

    traverse(cur.left);
    tail.right = cur;
    tail = tail.right;
    traverse(cur.right);
  };

  traverse(root);
  return newRoot.right;
};

// 탐색마다 새로운 node를 생성
var increasingBST = function (root) {
  let newRoot = new TreeNode(0);
  let tail = newRoot;

  const traverse = (cur) => {
    if (!cur) return;

    traverse(cur.left);
    tail.right = new TreeNode(cur.val);
    tail = tail.right;
    traverse(cur.right);
  };

  traverse(root);
  return newRoot.right;
};