class Program {
    public static BinaryTree flattenBinaryTree(BinaryTree node) {
	// O(n) time | O(d) space d -> depth of tree
        flatten(node, null, null);
        while (node.left != null) node = node.left;
        return node;
    }

    static void flatten(BinaryTree node, BinaryTree left, BinaryTree right) {
        boolean isLeftMost = node.left == null && left != null;
        boolean isRightMost = node.right == null && right != null;
        boolean shouldExploreLeft = node.left != null;
        boolean shouldExploreRight = node.right != null;

        if (isLeftMost) {
            node.left = left;
            left.right = node;
        } else if (shouldExploreLeft) flatten(node.left, left, node);

        if (isRightMost) {
            node.right = right;
            right.left = node;
        } else  if (shouldExploreRight) flatten(node.right, node, right);
    }

  // This is the class of the input root. Do not edit it.
  static class BinaryTree {
    int value;
    BinaryTree left = null;
    BinaryTree right = null;

    public BinaryTree(int value) {
      this.value = value;
    }
  }
}