Given a binary search tree, print all combination of inputs that forms the same BST

Question

For example,

input binary tree is

     2 
3         1 

we need to print all possible combinations that for the same binary tree structure (tree balancing not needed)

231, 213

Note : 123 is not a valid output since , it will change the tree structure .

It gets complicated if the pattern is lengthier.

another example

         5 
      3     7
   2    4  6   8

in this case

5 3 7 2 4 6 8

5 3 2 4 7 6 8

5 7 3 2 4 6 8

...............

I would like to know if there is any algorithm to find patterns which gives the same binary tree.

Answer 1

Here is a simple algorithm using backtracking in Python. It assumes an implementation of a binary search tree with an insert operation. Each node has a value at node.value, and possibly children at node.left and node.right.

def get_children(node):
    children = []
    if node.left is not None:
        children.append(node.left)
    if node.right is not None:
        children.append(node.right)
    return children

def print_permutations(possibilities, string):
    if len(possibilities) == 0:
        print(string)
        return

    for i in range(len(possibilities)):
        node = possibilities[i]
        del possibilities[i]
        new_possibilities = get_children(node) + possibilities
        print_permutations(new_possibilities, string + " " + str(node.value))
        possibilities.insert(i, node)

The idea is that every time you select a node from your list of possible candidates for the next number, you add that node's children to your list of possible candidates. Once there are no more candidates, you have arrived at one possible ordering.

You might call it like this:

b = BinarySearchTree()
b.insert(5)
b.insert(3)
b.insert(7)
b.insert(2)
b.insert(4)
b.insert(6)
b.insert(8)

print_permutations(get_children(b.root), str(b.root.value))

And it will output:

5 3 2 4 7 6 8
5 3 2 4 7 8 6
5 3 2 7 6 8 4
5 3 2 7 6 4 8
5 3 2 7 8 6 4
...

Answer 2

This problem is harder than it looks on the surface.

Consider the tree from your first example:

  2
1   3

As you say, there are two possible orderings of input: 2,1,3, and 2,3,1. The rule is: root, then children in any order.

But that's too easy. To see the full complexity of the problem, you have to extend it to another level. Thus, your second example:

      5 
   3     7
2    4  6   8

There are in general two ways to construct this tree: breadth first, or depth first. To do it breadth first, you repeatedly apply the "root first, then children in any order" rule. Thus:

5,3,7,2,4,6,8
5,3,7,2,4,8,6
5,3,7,2,6,4,8
...
5,7,3,8,6,4,2

At each level there are (2^k)! permutations, where k is the level. So there is 1 permutation at the root, two permutations at the second level (k == 1), 24 permutations at the next level, etc.

But doing this breadth first will not generate all of the possible valid inputs. For example, 5,3,2,4,7,6,8 is perfectly valid. To get all of the valid inputs, you have to include depth-first construction, as well. And here things get kind of interesting.

You can generate a pre-order traversal of the tree: 5,3,2,4,7,6,8, or a reverse pre-order traversal: 5,7,6,8,3,2,4. The rule here is root, then traverse the children depth-first in any order.

But that doesn't cover the odd case of 5,3,2,7,8,4,6, which just kind of skips around but makes sure that a node's parent is supplied before any of its children.

I don't have a complete solution, but I can give you the beginning of an algorithm. Consider the case of randomly generating a valid input sequence. You can do that with a loop:

nodes_array = create an array of nodes that can be selected
output_array = array of selected nodes

add root to nodes_array
while nodes_array is not empty
    temp = randomly select node from nodes_array, and remove it
    if temp.left != null
        add temp.left to nodes_array
    if temp.right != null
        add temp.right to nodes_array
    append temp to output_array
end while

That should always generate a valid input because a child node is never added to the output array unless its parent has already been selected.

The problem of generating all valid combinations, then, becomes a problem of changing that random selection step so that at each level it generates all possible permutations of the nodes_array. Generating permutations is a solved problem. Applying that recursively, though, will take a bit of thought.