CtCI 6h Edition, Problem 4.9: BST Sequences.

CtCI-6h-problem-4.9.markdown

Problem 4.9. BST Sequences: 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 possible arrays that could have led to this tree.

Solution.

Let's start with an example.

    4
   / \
  2   5 
 / \   \
1   3   6

To construct this tree we must insert the node 4 first. This node is always going to be the first element in each of the possible solution. Lets remove this node from the tree.

  2    5    
 / \    \
1   3    6

To continue construcing the tree from the example we now have a choice of eather inserting 2 or 5. Notice that both are the roots of the respective subtrees. Lets start with node 2 and remove it from the tree.

1   3   5
         \
          6

We are left with 3 subtrees. We now have a choice of removing either 1, 3 or 5.

You can cleary see that there is an inductive step which we can use to implement our solution:

start with a root of the tree (the only valid choice)

for each of the current valid choices:
- remove one of the roots (valid choices), add its children to the set of choices
- recursively find all possible solutions for the new set of choices
- append the root to the head of each of those solutions

the recursion ends when there are no remaining nodes (choices) left

Implementation.

Here's an actual code written in Swift. It uses arrays, but it might make sense to use lists instead. The key to implementing the algorithm is to keep the array of all choices after removing the node from the tree.

func bstSequences<T>(_ tree: Node<T>) -> [[T]] {
    return bstSequences([tree])
}

func bstSequences<T>(_ roots: [Node<T>]) -> [[T]] {
    var output = [[T]]()
    
    for i in roots.indices {
        var choices = roots
        let root = choices.remove(at: i)
        choices.append(contentsOf: root.children)
        
        if choices.count > 0 {
            for s in bstSequences(choices) {
                output.append([root.value] + s)
            }
        } else {
            output.append([root.value]) // end recursion
        }
    }
    
    return output
}

Testing the solution:

for s in bstSequences(Node.makeBST(from: [4, 2, 1, 3, 5, 6])!) {
    print(s)
}

Output:

[4, 2, 5, 1, 3, 6]
[4, 2, 5, 1, 6, 3]
[4, 2, 5, 3, 1, 6]
[4, 2, 5, 3, 6, 1]
[4, 2, 5, 6, 1, 3]
[4, 2, 5, 6, 3, 1]
[4, 2, 1, 5, 3, 6]
[4, 2, 1, 5, 6, 3]
[4, 2, 1, 3, 5, 6]
[4, 2, 3, 5, 1, 6]
[4, 2, 3, 5, 6, 1]
[4, 2, 3, 1, 5, 6]
[4, 5, 2, 6, 1, 3]
[4, 5, 2, 6, 3, 1]
[4, 5, 2, 1, 6, 3]
[4, 5, 2, 1, 3, 6]
[4, 5, 2, 3, 6, 1]
[4, 5, 2, 3, 1, 6]
[4, 5, 6, 2, 1, 3]
[4, 5, 6, 2, 3, 1]

Here's a tree implementation used in the solution:

public class Node<T> {
    public var value: T
    public var left: Node<T>?
    public var right: Node<T>?

    public var children: [Node<T>] {
        var output = [Node<T>]()
        if let left = left { output.append(left) }
        if let right = right { output.append(right) }
        return output
    }
    
    public init(_ value: T) {
        self.value = value
    }
}

Excellent @kean, here's my version of your code in Java:

public List<List<Integer>> bstSequences(Node tree) {
       List<Node> list = new ArrayList<>();
       list.add(tree);
       return bstSequences(list);
   }

private List<List<Integer>> bstSequences(List<Node> roots) {
       List<List<Integer>> output = new ArrayList<>();
       for(var i : roots) {
           List<Node> choices = new ArrayList<>(roots);
           Node root = choices.remove(choices.indexOf(i));
           if(root.getLeft() != null) choices.add(root.getLeft());
           if(root.getRight() != null)  choices.add(root.getRight());

           if(choices.size() > 0) {
               for(var s : bstSequences(choices)) {
                   List<Integer> list = new ArrayList<>();
                   list.add(root.getValue());
                   list.addAll(s);
                   output.add(list);
               }
           } else {
               List<Integer> list = new ArrayList<>();
               list.add(root.getValue());
               output.add(list); // end recursion
           }
       }
       return output;
   }