Given a binary search tree, print all possible arrays that produce the tree. An array produces a tree by inserting the array’s elements one by one into the tree. The elements are taken from the array from left to right.

Example. Consider the following binary search tree.

   4
/ \
2 9

Its corresponding arrays are the following.

[4, 9, 2]
[4, 2, 9]

Input. The input file consists of positive integer N on the first line followed by N test cases. The first line of any given test case consists of a pair of positive integers M and R separated by a single space. Integer M indicates the number of edges in the binary search tree and R is the root of the tree. The M lines that remain in the test case consist of pairs of positive integers P and C corresponding to an edge that goes from parent node P to child node C. The following input file corresponds to the example.

1
2 4
4 2
4 9

Output. The output consists of all possible arrays for each test case. The arrays that correspond to a given test case must appear in lexicographical order. Each array must appear on a single line. To print an array, print the elements separated by space. For example, the corresponding is the output for the previous input.

4 2 9
4 9 2

Check your solution online

Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

Click here to check your solution online at The Book of Problems.

2017-10-08 The Book of Problems currently supports Ruby, Python and now Elixir. More languages will come soon. If there is a language you’d like to use, drop me a line in the comments section.

Solution

We build each array from left to right by choosing for every position one node out of a set of possible choices for that position. The set of possible choices for a position is given by the corresponding array prefix. We illustrate the method with the following tree.

We visit the tree starting from the root node. We create array $@acc_0@$. We collect the children of the root in set $@cho_0@$ as possible choices to visit next. The state is the following.

We choose to visit node 3 next. We append 3 to the end of $@acc_0@$ and label the new array $@acc_1@$. We remove 3 from set of choices $@cho_0@$, add the children of 3, and label the new set as $@cho_1@$. The state is the following.

We choose to visit node 8 next. We append 8 to the current array and label the result $@acc_2@$. We remove 8 from the set of choices and label the result $@cho_2@$. The state is the following.

We choose to visit node 1 next. The state is the following.

We choose to visit node 4 next. There are no further choices. We have our first possible array. The state is the following.

To generate the rest of the possible arrays, we backtrack until we can make a different choice and apply the method again.

Implementation

Here is a Ruby implementation.

#!/usr/bin/env ruby

def apa children, cho, acc, curr
children[curr].each { |c| cho[c] = 1 } if !!children[curr]
r = []
if cho.empty?
r << acc + [curr]
else
cho.keys.each do |k|
cho.delete(k)
acc.push curr
r += apa(children, cho, acc, k)
acc.pop
cho[k] = 1
end
end
children[curr].each { |c| cho.delete c } if !!children[curr]
return r
end


def main
n = readline.to_i

while (n -= 1) >= 0
m, r = readline.strip.split(' ').map(&:to_i)
children = {}
while (m -= 1) >= 0
p, c = readline.strip.split(' ').map(&:to_i)
children[p] ||= []
children[p] << c
end
apa(children, Hash.new, [], r).sort.each { |a| puts a.join(' ') }
end
end

main

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments