Program.java

package AlgoExSolutions.VeryHard.FlattenBinaryTree;

// import java.util.*;

/**
 * * Flatten Binary Tree
 */
class Program {
  /**
   * * TC: O(n)
   * * SC: O(d)
   */
  public static BinaryTree flattenBinaryTree(BinaryTree root) {
    // Write your code here.
    return flattenBinaryTreeHelper(root)[0];
  }

  private static BinaryTree[] flattenBinaryTreeHelper(BinaryTree root) {
    BinaryTree leftNode = null, rightNode = null;

    if (root.left == null) leftNode = root;
    else {
      BinaryTree[] lstNodes = flattenBinaryTreeHelper(root.left);
      connectNodes(lstNodes[1], root);
      leftNode = lstNodes[0];
    }

    if (root.right == null) rightNode = root;
    else {
      BinaryTree[] rstNodes = flattenBinaryTreeHelper(root.right);
      connectNodes(root, rstNodes[0]);
      rightNode = rstNodes[1];
    }

    return new BinaryTree[] {leftNode, rightNode};
  }

  private static void connectNodes(BinaryTree left, BinaryTree right) {
    left.right = right;
    right.left = left;
  }

  /**
   * * TC: O(n)
   * * SC: O(n)
   */
  // public static BinaryTree flattenBinaryTree(BinaryTree root) {
  // 	List<BinaryTree> nodes = getNodes(root);

  // 	for (int i = 1; i < nodes.size(); i++) {
  // 		BinaryTree leftNode = nodes.get(i - 1), rightNode = nodes.get(i);

  // 		leftNode.right = rightNode;
  // 		rightNode.left = leftNode;
  // 	}

  //   return nodes.get(0);
  // }

  // private static List<BinaryTree> getNodes(BinaryTree root) {
  // 	List<BinaryTree> nodes = new ArrayList<>();
  // 	getNodes(root, nodes);
  // 	return nodes;
  // }

  // private static void getNodes(BinaryTree root, List<BinaryTree> nodes) {
  // 	if (root != null) {
  // 		getNodes(root.left, nodes);
  // 		nodes.add(root);
  // 		getNodes(root.right, nodes);
  // 	}
  // }

  // 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;
    }
  }
}