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

Thank you for publishing this!
I converted your solution to C# for those who feel more comfortable with it, here.

@kean, @OfirD1
Thanks for sharing.

Can u give in c++, please

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

from typing import List
import unittest

class TreeNode:
    def __init__(self, value = None):
        self.value = value
        self.left = None
        self.right = None

def bst_sequences(root: TreeNode):
    def __visit(roots: List):
        output = []
        for root in roots:
            choices = [choice for choice in roots if choice != root]
            if root.left:
                choices.append(root.left)
            if root.right:
                choices.append(root.right)

            if len(choices) > 0:
                sequences = __visit(choices)
                for sequence in sequences:
                    output.append([root.value] + sequence)
            else:
                output.append([root.value])
        return output

    return __visit([root])

class BSTTests(unittest.TestCase):
    @staticmethod
    def create_tree() -> TreeNode:
        node = TreeNode(1)
        node.left = TreeNode(2)
        node.right = TreeNode(3)
        node.right.right = TreeNode(4)
        return node

    def test_bst_sequences(self):
        root = BSTTests.create_tree()
        sequences = bst_sequences(root)
        actual_result  = set(tuple(sequence) for sequence in sequences)
        expected_result = set(tuple(item) for item in [[1, 2, 3, 4],[1, 3, 2, 4],[1, 3, 4, 2]])
        self.assertSetEqual(actual_result, expected_result)

Finally found an intuitive approach!! Thanks a lot!
Implementation in C++ (Here's a link to full code)

void bstSeq() {
  list<Node*> startingList, emptyList;
  startingList.push_back(root);
  bstSeq(startingList, emptyList);
}

void bstSeq(list<Node *> currChoices, list<Node *> output) {
  if(currChoices.size() == 0) {
    for(auto node : output) {
      cout << node->data << " ";
    }
    cout << endl;
  } else {
    for(auto node : currChoices) {
      list<Node*> temp1 = currChoices;
      list<Node*> temp2 = output;
      temp1.remove(node);
      if(node->left != NULL) temp1.push_back(node->left);
      if(node->right != NULL) temp1.push_back(node->right);
      temp2.push_back(node);
      bstSeq(temp1, temp2);
    }
  }
}

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