Directi Interview Question
Senior Software Development EngineersCountry: India
public class PrintCombinationOfTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode node1 = new TreeNode(4);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(6);
TreeNode node4 = new TreeNode(1);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(7);
TreeNode node7 = new TreeNode(2);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node4.right = node7;
node3.left = node5;
node3.right = node6;
PrintCombinationOfTree p = new PrintCombinationOfTree();
List<List<Integer>> result = p.getTreeList(node1);
for (List l: result) {
System.out.println(l);
}
}
private List<List<Integer>> getTreeList(TreeNode node) {
if (node.left == null && node.right == null) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
temp.add(node.data);
result.add(temp);
return result;
}
List<List<Integer>> left = null;
List<List<Integer>> right = null;
if (node.left !=null) {
left = getTreeList(node.left);
}
if (node.right !=null) {
right = getTreeList(node.right);
}
if (left != null && right != null) {
return getList(node, left, right);
}
return getList(node, left!=null?left:right);
}
private List<List<Integer>> getList(TreeNode root, List<List<Integer>> left, List<List<Integer>> right) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> l: left) {
for (List<Integer> r : right) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(root.data);
temp.addAll(l);
temp.addAll(r);
result.add(temp);
}
}
for (List<Integer> r: right) {
for (List<Integer> l : left) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(root.data);
temp.addAll(r);
temp.addAll(l);
result.add(temp);
}
}
return result;
}
private List<List<Integer>> getList(TreeNode root, List<List<Integer>> list) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> l: list) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(root.data);
temp.addAll(l);
result.add(temp);
}
return result;
}
}
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
To get the same BST, a number should be listed only after its parent.
This is identical to traversing through the BST. So the permutations can be arrived at by performing all possible traversals of the tree.
//Traverse the tree in all possible permutations
//Take a node from the boundary and
// append it to the traversal.
// Remove the node from the boundary and
// add its children. Recurse with the new boundary.
//Iterate with all nodes in the bounbdary,
// concatenate and return the results
//Initially, the traversal will be empty,
// and the boundary will be the root
tp.traverseall = function (boundary, traversal) {
var results = [], i, permutation, node;
traversal = traversal || [];
if(boundary.length === 0) {
//Entire tree has been traversed
//Return the input traversal itself as the only result
return [traversal]
}
for (i=0; i< boundary.length; i++) {
permutation = {
boundary:null,
traversal:null,
results:null
};
//Remove the ith node
permutation.boundary = boundary.slice();
permutation.boundary.splice(i, 1);
node = boundary[i];
//Add its children
if(node.left) {
permutation.boundary.push(node.left);
}
if(node.right) {
permutation.boundary.push(node.right);
}
//Fork a new traversal from the input traversal and
//append the current node to it.
permutation.traversal = traversal.slice();
permutation.traversal.push(node.data)
//Recursse
permutation.results = tp.traverseall(permutation.boundary, permutation.traversal);
//Concatenate results from all iterations
results = results.concat(permutation.results);
}
return results;
}
#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
#include<list>
#include<conio.h>
using namespace std;
class node
{
public:
int x;
node *left , *right ;
};
node* create_tree(vector<int> v)
{
node* root = new node ;
root->x = v[0] ;
root->left = root->right = NULL ;
for(int i=1;i<v.size();i++)
{
node *temp = new node ;
temp->x = v[i] ;
temp->left = temp->right = NULL ;
node *temp2 , *temp1 = root ;
while(temp1 != NULL)
{
temp2 = temp1 ;
if(temp->x < temp1->x)
temp1 = temp1->left ;
else
temp1 = temp1->right ;
}
if(temp->x < temp2->x)
temp2->left = temp ;
else
temp2->right = temp ;
}
return root ;
}
void inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp->left) ;
cout<<temp->x<<" " ;
inorder(temp->right) ;
}
}
map<int,vector<int> > edge_store(node* temp,map<int,vector<int> > v)
{
if(temp!= NULL)
{
if(temp->left != NULL)
v[temp->x].push_back(temp->left->x) ;
if(temp->right != NULL)
v[temp->x].push_back(temp->right->x) ;
v = edge_store(temp->left,v) ;
v = edge_store(temp->right,v) ;
}
return v ;
}
void print_edge(vector<int> incl,map<int,vector<int> > ve,list<int> l)
{
if(l.empty())
{
for(int i=0;i<incl.size();i++)
cout<<incl[i]<<" " ;
cout<<endl ;
}
list<int>::iterator it = l.begin();
while(it != l.end())
{
vector<int> temp(incl) ;
list<int> templist(l) ;
for(int i=0;i<ve[*it].size();i++)
templist.push_back(ve[*it][i]) ;
temp.push_back(*it) ;
list<int>::iterator lit ;
for(lit = templist.begin();lit != templist.end();lit++)
{
if(*it == *lit)
break ;
}
templist.erase(lit) ;
it++ ;
print_edge(temp,ve,templist) ;
}
}
int main()
{
int n;
cin>>n;
vector<int> v(n) ;
for(int i=0;i<n;i++)
cin>>v[i] ;
node *root = create_tree(v) ;
map<int,vector<int> > ve ;
ve = edge_store(root,ve) ;
vector<int> incl;
list<int> l;
list<int>::iterator it ;
for(int i=0;i<ve[v[0]].size();i++)
l.push_back(ve[v[0]][i]) ;
incl.push_back(v[0]) ;
print_edge(incl,ve,l) ;
return 0;
}
from __future__ import print_function
import itertools
import re
import sys
def iter_binary_tree_permutations(numbers):
"""Iterates all permutations of a given sequence such that the permutation
makes the same binary search tree as the original sequence.
"""
if not numbers:
yield []
return
root = numbers[0]
left = []
right = []
for n in itertools.islice(numbers, 1, None):
if n < root:
left.append(n)
else:
right.append(n)
for lp, rp in itertools.product(iter_binary_tree_permutations(left),
iter_binary_tree_permutations(right)):
for p in iter_splices(lp, rp):
yield [root] + p
def iter_splices(a, b):
"""Iterates all splices for two given sequences.
>>> for splice in iter_splices([1, 2], [3, 4]): print(splice)
[1, 2, 3, 4]
[3, 1, 2, 4]
[3, 4, 1, 2]
[1, 3, 2, 4]
[1, 3, 4, 2]
[3, 1, 4, 2]
"""
if not a:
yield b
return
indices = range(len(b) + 1)
for partitions in iter_partitions(a):
k = len(partitions)
for pivots in itertools.combinations(indices, k):
ret = b[:pivots[0]]
for i in xrange(k - 1):
ret.extend(partitions[i])
ret.extend(b[pivots[i]:pivots[i + 1]])
ret.extend(partitions[k - 1])
ret.extend(b[pivots[k - 1]:])
yield ret
def iter_partitions(a):
"""Iterates all partitions for a given sequence.
>>> for partitions in iter_partitions([1, 2, 3]): print(partitions)
[[1, 2, 3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1], [2], [3]]
"""
yield [a]
indices = range(1, len(a))
for num_pivots in xrange(1, len(a)):
for pivots in itertools.combinations(indices, num_pivots):
ret = [a[:pivots[0]]]
for i in xrange(num_pivots - 1):
ret.append(a[pivots[i]:pivots[i + 1]])
ret.append(a[pivots[num_pivots - 1]:])
yield ret
if __name__ == '__main__':
numbers = [4, 3, 1, 2, 6, 5, 7]
# numbers = [int(n) for n in re.split(r'\s*,\s*', sys.stdin.read().strip())]
for p in iter_binary_tree_permutations(numbers):
print(p)
No explanation, no algo, Do you really think that everyone want to debug your code and try to understand what you had in mind? Post your idea first its more important then the code.
Well, it's a simple, recursive solution.
Suppose that for an integer sequence S, there is a function f that returns a set of sequences f(S) where all sequences in f(S) makes the same binary search tree.
If S has only one element, then f(S) is a set of size 1 and it has S as an element.
If S has more than one element, we can split it into one element r and two sequences A and B, where r is the first element of S, A is such that x < r for all x in A, B is such that x >= r for all x in B. If you make a binary search tree from S, then r would be the root and all elements in A will be descendants of the left child of the root and all elements in B will be descendants of the right child.
Now we can create new sequences which make the same tree by "mixing" elements A and B and inserting r at the front, but preserving the orders in A and B; for example, if A is [1, 2, 3], and B is [4, 5, 6], mixing A and B would produce sequences like [1, 4, 2, 5, 3, 6] and [1, 2, 4, 3, 5, 6].
But note that in the tree of S, A and B each makes a subtree of their own. Therefore we need to mix all combinations of f(A) and f(B).
Here is the summary of the algorithm:
For an integer sequence S, f(S) is a set of sequences which make the same binary tree as S.
If the size of S is 1, f(S) = {S}.
If the size of S is more than 1, split S into r, A, B where r is the first element of S, A is a subsequence of S where x < r for all x in A, B is a subsequence of S where x >= r for all x in B. Then f(S) = {X | X = (r, W)} for all W ∈ g(Y, Z) where Y ∈ f(A), Z ∈ f(B), and g(Y, Z) is a function returning a set of sequences which have Y and Z as subsequences.
Though several insertion sequences can result into the same BST, a simple fact that can be concluded by observing is that:
as long as for any subBST the root is inserted before its subtrees, we can build the same BST after changing the insertion sequence.
It's like in the topological graph A->B and A->C, all we need to make sure is that A is done before B and C, while the order of B and C does not matter.
Now let's take the insertion sequence in the example of the problem,
the tree structure is like this:
to build the same BST, all we need to maintain after changing the insertion sequence is such relative order:
4->3 and 4->6
3->1
1->2
6->5 and 5->7
To get all the insertion sequences that can result into given BST, we can
(1)recursively get all the insertion sequences of the subtrees
(2)merge subtrees' insertion sequence into one while keeping each sequence's relative order
(3)push the root's value into the merged sequence's front
code in C++:
- uuuouou April 21, 2014