Print all possible sequences that could have created this BST I was working through Cracking The Coding interview, and I couldn't wrap my brain around their solution to one of the problems, so I ended up coming up with my own that, IMHO, is a lot cleaner and easier to read. Would love your feedback. Here is the actual problem:

"A binary search tree was created by traversing through an array from left to right and inserting each element. Given a binary search tree with distinct elements, print all of the arrays that could have led to this tree."

In other words, what are all of the possible sequences of values that could have led to this tree.

For reference, here is a link to the 'official' solution.

And here is what I came up with

public class AllSequences {
public LinkedList&lt;LinkedList&lt;TreeNode&gt;&gt; allSeqs;

public AllSequences(TreeNode root) {
    allSeqs = new LinkedList&lt;&gt;();
    LinkedList&lt;TreeNode&gt; pre = new LinkedList&lt;&gt;();
    LinkedList&lt;TreeNode&gt; poss = new LinkedList&lt;&gt;();

    buildSeqs(pre, poss, root);
    for (LinkedList&lt;TreeNode&gt; ll : allSeqs) {
        for (TreeNode n : ll) {
            System.out.print(n.data + " ");
        }
        System.out.println();
    }
}

private void buildSeqs(LinkedList&lt;TreeNode&gt; pre, LinkedList&lt;TreeNode&gt; poss, TreeNode root) {
    pre.add(root);
    if (root.left != null) {
        poss.add(root.left);
    }
    if (root.right != null) {
        poss.add(root.right);
    }

    if (poss.isEmpty()) {
        allSeqs.add(pre);
    }

    for (TreeNode n: poss) {
        LinkedList&lt;TreeNode&gt; temp = (LinkedList&lt;TreeNode&gt;) pre.clone();
        LinkedList&lt;TreeNode&gt; ptemp = (LinkedList&lt;TreeNode&gt;) poss.clone();
        ptemp.remove(n);
        buildSeqs(temp, ptemp, n);
    }
}

public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(15);
    root.left.right = new TreeNode(7);
    root.left.left = new TreeNode(3);

    AllSequences all = new AllSequences(root);
}
}


Granted mine ends up with a set of LinkedLists of possible input sequences, not arrays, but it would be easy enough to convert that if the interviewer was a stickler about it. It seems to correctly print out for all of my hand-coded, relatively small test cases.
public class Solution {
    ArrayList&lt;LinkedList&lt;Long&gt;&gt; result;
    /*Return the children of a node */
    ArrayList&lt;TreeNode&gt; getChilden(TreeNode parent) {
        ArrayList&lt;TreeNode&gt; child = new ArrayList&lt;TreeNode&gt;();
        if(parent.left != null) child.add(parent.left);
        if(parent.right != null) child.add(parent.right);
        return child;
    }
    /*Gets all the possible Compinations*/
    void getPermutations(ArrayList&lt;TreeNode&gt; permutations, LinkedList&lt;Long&gt; current) {
        if(permutations.size() == 0) {
            result.add(current);
            return;
        }
        int length = permutations.size();
        for(int i = 0; i &lt; length; i++) {
            TreeNode node = permutations.get(i);
            permutations.remove(i);
            ArrayList&lt;TreeNode&gt; newPossibilities = new ArrayList&lt;TreeNode&gt;();
            newPossibilities.addAll(permutations);
            newPossibilities.addAll(getChilden(node));
            LinkedList&lt;Long&gt; newCur = new LinkedList&lt;Long&gt;();
            newCur.addAll(current);
            newCur.add(node.val);
            getPermutations(newPossibilities, newCur);
            permutations.add(i,node);
        }
    }

    /*This method returns a array of arrays which will lead to a given BST*/
    ArrayList&lt;LinkedList&lt;Long&gt;&gt; inputSequencesForBst(TreeNode node) { 
        result = new ArrayList&lt;LinkedList&lt;Long&gt;&gt;();
        if(node == null)
            return result;
        ArrayList&lt;TreeNode&gt; permutations = getChilden(node);
        LinkedList&lt;Long&gt; current = new LinkedList&lt;Long&gt;();
        current.add(node.val);
        getPermutations(permutations, current);
        return result;
    }
}


My solution. Works perfectly.