Reconstruct a binary tree from traversal data - EPI

Reconstruct a binary tree from traversal data

ReconstructBinaryTreePreInOrdersTemplate.java
  private static <T> BinaryTree<T> reconstructPreInOrdersHelper(
      ArrayList<T> pre, int preS, int preE, ArrayList<T> in, int inS, int inE) {
    if (preE > preS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(pre.get(preS));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;

      return new BinaryTree<T>(pre.get(preS), reconstructPreInOrdersHelper(pre,
          preS + 1, preS + 1 + leftTreeSize, in, inS, it),
          reconstructPreInOrdersHelper(pre, preS + 1 + leftTreeSize, preE, in,
              it + 1, inE));
    }
    return null;
  }

  public static <T> BinaryTree<T> reconstructPreInOrders(ArrayList<T> pre,
      ArrayList<T> in) {
    return reconstructPreInOrdersHelper(pre, 0, pre.size(), in, 0, in.size());
  }
ReconstructBinaryTreePostInOrdersTemplate.java
  private static <T> BinaryTree<T> reconstructPostInOrdersHelper(
      ArrayList<T> post, int postS, int postE, ArrayList<T> in,
          int inS, int inE) {
    if (postE > postS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(post.get(postE - 1));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;
      return new BinaryTree<T>(post.get(postE - 1),
      // Recursively build the left subtree.
          reconstructPostInOrdersHelper(post, postS, postS + leftTreeSize, in,
              inS, it),
          // Recursively build the right subtree.
          reconstructPostInOrdersHelper(post, postS + leftTreeSize, postE - 1,
              in, it + 1, inE));
    }
    return null;
  }

  public static <T> BinaryTree<T> reconstructPostInOrders(ArrayList<T> post,
      ArrayList<T> in) {
    return reconstructPostInOrdersHelper(post, 0, post.size(), in, 0, in.size());
  }

Reconstruct a binary tree from a preorder traversal with marker

ReconstructPreorderWithNullTemplate.java
  public static <T> BinaryTree<T> reconstructPreorder(ArrayList<T> preorder) {
    LinkedList<BinaryTree<T>> s = new LinkedList<BinaryTree<T>>();
    for (int i = preorder.size() - 1; i >= 0; i--) {
      if (preorder.get(i) == null) {
        s.push(null);
      } else {
        BinaryTree<T> l = s.pop();
        BinaryTree<T> r = s.pop();
        s.push(new BinaryTree<T>(preorder.get(i), l, r));
      }
    }
    return s.peek();
  }

  // @exclude

  private static <T> void genPreorderWithNull(BinaryTree<T> n, ArrayList<T> p) {
    if (n == null) {
      p.add(null);
      return;
    }

    p.add(n.getData());
    genPreorderWithNull(n.getLeft(), p);
    genPreorderWithNull(n.getRight(), p);
  }