How to generate all possible binary tree in reverse lexicographic order

Standard

Suppose we are representing binary as L and R array, for example
The tree would be represented then
1            L[1]=2, R[1]=4
/  \           L[2]=0, R[2]=3
2   4        L[3]=0, R[3]=0
\             L[4]=0, R[4]=0
3

Now, if we read tree in preorder, in such a way that if node present it print 1 otherwise 0 then this tree will also be represented as 110100100. Now the problem we are going to solve here is: “ if we have to generate all possible binary tree for a give number of node in such a way that if we traverse the tree in preorder just described then it should be in reverse lexicographic order.

Now, first we will develop the algo then will code it.

Our first step will be to observe the pattern and see what will be the next generated tree for a given tree. Suppose we have this tree

                       1

                  /

             2

           /

        3

tree in 1,0 format : 1110000

then the next generated tree in the reverse lexicographic order will be this

                         1

                     /

                  2

                     \

                       3

tree in 1,0 format : 1101000

After looking at then newly generated tree, we can find that node 3 has moved and its moved from left of 2 to right of 3.  Let us generate one more tree from the last generated tree and the new tree will look like this:

                1

            /       \

          2            3

tree in 1,0 format : 1100100 (Note: observe this no for all the generated tree, you will find its decreasing)

and next  tree generated from this tree is:

               1

             /   \

        null      2

                   /      \

              3          null

tree in 1,0 format : 1011000 (Note: observe this no for all the generated tree, you will find its decreasing)

If we compare with the last generated one then we will find that this time node 2 has moved and now node 3 is left child of node 2.  If we generate  some more trees then we will find that this algo:

1. take the nth node and try to find the best position for it i.e. the next possible position for it in preorder.

2. if we are not able to find any position for nth node then try to find for n-1 th node and moved the node there

and then we make all node greater then this left child of its parent.

For example :-

1 we take the first generated tree as an example here:

1. let us take the nth node , 3 in this case, now try to find the next possible position for it in the tree after traversing it in preorder then we will find that it it is the right of 2nd node.

2. move the 3 rd node to right of 2nd node and since it has no child node, hence this is the answer.

2. Now try, the last generated tree:

1. let us take the nth node first here i.e. 3rd node in this case, now if we try to next possible position. We see there is no possible next position for so

2. try the node higher then it i.e. 2nd node. We find that next possible position for it is right of 1. Now shift 2nd to this new position and move 3 rd as its left child, if we have 4 th node then we would have made it left of 3rd.

The most important this, we have to do now, is to find the way to find the next possible position for the given node. After,  we do pre-order traversal of the tree then we will find that the 3 rd node traversed after traversing the selected node is the possible position for it. For example,

take the example of first generated tree:-

                            1

                       /       \

                      2           null 4

                  /    \

              3         null 3

             /    \

     null  1   null 2

now if we try to find , the possible position for 3 we see that after traversing node 3 in pre-order, we traverse null 1 first then null 2 and then null3 which is the possible position and which is exactly third node traversed after traversing node 3. Hence our logic is correct in this example.

Now, we consider the last generated tree, the parent tree is

                                      1

                                  /      \

                              2             3

                         /     \             /   \

                 null1  null2     null3  null4

Now, we try to find,  best  position for nth node, i.e. 3 rd node, now if we do pre-order traversal, then we find that after traversing node 3rd we can only 2 nodes which are its child and hence there is no possible shift for node 3 rd hence we will do the same for node 2 nd and we will find that 3 rd node traversed after traversing node 2 is the node where currently node 3 is, hence we shift 2 to this new position and make node 3 its left child and if we would has 4 th node then it would have been the left child of node 3rd and so on.

Before we start coding, one more point left to discuss is: from where to start, what actually I mean is what will be the first base tree?

For, generating the reverse lexicographic order  tree, the firs tree should be the left linear tree i.e.

                                                   1

                                            /

                                    2

                                 /

                            3

                        .

                      .

                  n

and the final tree will be right linear tree i.e.

1

   \

      2

        \

           3

               .

                  .

                   n


package edu.temple.pt.assignment;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* This program is written as part of the assignment 5 question 1. It provides APIs to generate the next binary tree for a given binary tree in
* reverse lexicographic order.
*
* Assignment:
* Assume the nodes of any n node binary tree are numbered from 1 to n in preorder. Arrays L and R will be used to represent the tree in memory as in the following example.
* Consider the tree with nodes 1, 2, 3 and 4 with 2 and 4 as 1’s left and right successors and 3 as 2’s right successor. Then L and R would be
* L[1]=2, R[1]=4
L[2]=0, R[2]=3
L[3]=0, R[3]=0
L[4]=0, R[4]=0

Write a program to generate all the binary trees with n nodes so that their representations, using n 0’s and n 1’s (i.e. n right and n left parentheses)
as discussed in class, would appear in reverse lexicographic order. The tree is represented in memory only by the L and R arrays. To do this, you should determine
what transformation is required on a tree that corresponds to the transformation on its parentheses representation to produce the successor tree in lexicographic
order, and then carry out this transformation on the tree in memory. Your program should output the L and R arrays for each tree and its corresponding n 0’s and n 1’s
representation. You should provide a number of samples for small n that are actual outputs of the program. In addition you should output the #of binary trees with n nodes.

<code>

* @author aakash
*
*/
public class ReversedLexicoGraphic {
/**
*
*/
public ReversedLexicoGraphic() {
super();
}
private int preOrderElementVisited[]=null;
private int elementVisitedPosition[]=null;

/**
* this method will do preorder traversal to the tree represented in LR array and will decide what is the next best position for
* the given element.
* @param binaryTreeInLRArray binary tree represented in LR array
* @param element element for which the best next position to be found
* @return -1 if it there is no suitable next position for it otherwise it will return positive number( if is is less than n(number of nodes in tree)
* then it means the index in left array otherwise return_value-n is the index for right array)
*/
private int findNextPositionForGivenElement(BinaryTreeInLRArray binaryTreeInLRArray,int element)
{
preOrderElementVisited=new int[binaryTreeInLRArray.getLeftArray().length*2+1];
elementVisitedPosition=new int[binaryTreeInLRArray.getLeftArray().length-1];
for(int i=0;i<elementVisitedPosition.length;i++)
elementVisitedPosition[i]=-1;
for(int i=0;i<preOrderElementVisited.length;i++)
preOrderElementVisited[i]=-1;
//int freeEntry=0;
int p=1;
Stack stack=new Stack();
int i=0;
int lastFreeEntry=-1;
int j=0;
boolean foundLastNode=false;
int countOfLeaveNodeAfterLastNode=0;
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
stack.push(p);

preOrderElementVisited[i++]=p-1;
if(binaryTreeInLRArray.getLeftArray()[p-1]==0&&foundLastNode)
{
//System.out.println(“calculating prev=”+lastFreeEntry+” when p=”+(p-1));
countOfLeaveNodeAfterLastNode++;
if(countOfLeaveNodeAfterLastNode>=3)
{
lastFreeEntry=p-1;
break;
}
}
if(binaryTreeInLRArray.getLeftArray()[p-1]!=0)
{
if(j=3)
{
lastFreeEntry=p-1+binaryTreeInLRArray.getLeftArray().length;
break;
}

}
else if(binaryTreeInLRArray.getRightArray()[p-1]!=0&&j<elementVisitedPosition.length-1)
elementVisitedPosition[j++]=p-1+binaryTreeInLRArray.getLeftArray().length;
p=binaryTreeInLRArray.getRightArray()[p-1];

}

}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{
preOrderElementVisited[i]=stack.peek()-1+binaryTreeInLRArray.getLeftArray().length;
r=binaryTreeInLRArray.getRightArray()[stack.peek()-1];
if(r==0&&foundLastNode)
{
//System.out.println(“calculating prev=”+lastFreeEntry+” when p=”+(p-1));
countOfLeaveNodeAfterLastNode++;
if(countOfLeaveNodeAfterLastNode==3)
{
lastFreeEntry=stack.peek()-1+binaryTreeInLRArray.getRightArray().length;
stack.removeAllElements();
return lastFreeEntry;
}

}
else if(r!=0&&j=2;element–)
{
BinaryTreeInLRArray tempBinaryTreeInLRArray=new BinaryTreeInLRArray(baseBinaryTreeInLRArray.getLeftArray().length);
for(int i=2;i<=element;i++)
{
int tempPosition=elementVisitedPosition[i-2];
modifyArrayAtPosition(tempBinaryTreeInLRArray, tempPosition, i);
}
position=findNextPositionForGivenElement(tempBinaryTreeInLRArray, element);
tempBinaryTreeInLRArray=null;
if(position!=-1)
break;
}

if(element==1||element==-1)
{
binaryTreeInLRArray=null;
return binaryTreeInLRArray;
}
// findNextPositionForGivenElement(baseBinaryTreeInLRArray, baseBinaryTreeInLRArray.getLeftArray().length);
// System.out.println(“position:”+position+” for element:”+element);
for(int i=2;i<element;i++)
{
int tempPosition=elementVisitedPosition[i-2];
modifyArrayAtPosition(binaryTreeInLRArray, tempPosition, i);
}

modifyArrayAtPosition(binaryTreeInLRArray, position, element);
for(int i=element+1;i<=binaryTreeInLRArray.getLeftArray().length;i++)
{
int tempPosition=i-2;
modifyArrayAtPosition(binaryTreeInLRArray, tempPosition, i);
}

}
else
{
for(int i=2;i=binaryTreeInLRArray.getLeftArray().length)
{
position-=binaryTreeInLRArray.getLeftArray().length;
binaryTreeInLRArray.getRightArray()[position]=element;
}
else
binaryTreeInLRArray.getLeftArray()[position]=element;
}
/**
* This method can be used to get the next binary tree in reverse lexicographic order.
*
* @param base the base tree from which the next binary tree will be generated
* @return null if there is no possible binary tree otherwise the new generated binary tree.
*/
public BinaryTreeInLRArray getNextBinaryTree(BinaryTreeInLRArray base)
{
if(base.getLeftArray().length<=1)
return null;
// BinaryTreeInLRArray nextLRBinaryTree=new BinaryTreeInLRArray(base.getLeftArray().length);

int prev=findNextPositionForGivenElement(base,base.getLeftArray().length);
// for(int i=0;i<preOrderElementVisited.length;i++)
// System.out.println(“\npreorder visit::”+preOrderElementVisited[i]);
// for(int i=0;i<elementVisitedPosition.length;i++)
// System.out.println(“element visited position::”+elementVisitedPosition[i]);
// System.out.println(“prev=”+prev);
// if(prev==-1)
// return null;

BinaryTreeInLRArray nextLRBinaryTree=modifiedPosition(base, prev);
return nextLRBinaryTree;
}
public List getAllReveresedLexicoGraphicBinaryTree(int n)
{
ArrayList binaryTreeInLRArrayList=new ArrayList();
if(n0″);
int L[]=new int[n];
int R[]=new int[n];
int j=2;
for(int i=0;i<n;i++)
{
R[i]=0;
if(j<=n)
L[i]=j++;
else
L[i]=0;
}
BinaryTreeInLRArray baseBinaryTreeInLRArray=new BinaryTreeInLRArray(L, R);
binaryTreeInLRArrayList.add(baseBinaryTreeInLRArray);
while((baseBinaryTreeInLRArray=getNextBinaryTree(baseBinaryTreeInLRArray))!=null)
binaryTreeInLRArrayList.add(baseBinaryTreeInLRArray);
return binaryTreeInLRArrayList;
}
public static void main(String args[])
{
// int R[]={5,0,4,0,0};
// int L[]={2,3,0,0,0};

int R[]={0,0,0,0};
int L[]={2,3,4,0};
BinaryTreeInLRArray binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.preOrderTraversal();

//binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree);
int i=1;
while((binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree))!=null)
{
binaryTree.preOrderTraversal();
i++;
System.out.println(“total generated count::”+i);
}
System.out.println(“total generated count::”+i);

/*
binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree);
//int i=1;
//while((binaryTree=new ReversedLexicoGraphic().getNextBinaryTree(binaryTree))!=null)
{
binaryTree.preOrderTraversal();
i++;
System.out.println(“total generated count::”+i);
}
System.out.println(“total generated count::”+i);

*/

}
}


package edu.temple.pt.assignment;

import java.util.Stack;

public class BinaryTreeInLRArray {

int L[]=null;
int R[]=null;

public void setLeftArray(int L[])
{
this.L=L;
return;
}
public void setRightArray(int R[])
{
this.R=R;
return;
}
public int[] getLeftArray()
{
return L;
}
public int[] getRightArray()
{
return R;
}

int visitedArray[]={-1};
public BinaryTreeInLRArray(int numberOfNodes) {
// TODO Auto-generated constructor stub
L=new int[numberOfNodes];
R=new int[numberOfNodes];
}
public BinaryTreeInLRArray(int L[],int R[]) {
// TODO Auto-generated constructor stub
if(L.length!=R.length)
throw new IllegalArgumentException(“Sorry! L and R array should be of equal length”);
this.L=L;
this.R=R;
}
private void visit(int i)
{
if(visitedArray[0]!=-1)
System.out.print(visitedArray[0]!=0?1:0);
visitedArray[0]=i;
}
private void cleanUpVisit(){
visitedArray[0]=-1;
}
private void printLRArray()
{
System.out.println(“\t[L]\t[R]”);
System.out.println(“\t—\t—“);
for(int i=0;i<L.length;i++)
System.out.println(“\t|”+L[i]+”|\t|”+R[i]+”|”);
}
public void preOrderTraversal()
{
printLRArray();
int p=1;
Stack stack=new Stack();
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
visit(p);
stack.push(p);
if(L[p-1]!=0)
p=L[p-1];
else
{
visit(L[p-1]);
p=R[p-1];
if(p==0)
visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{

r=R[stack.peek()-1];
if(r==0)
visit(r);
}
else
r=0;

}while(!stack.isEmpty()&& q==r);
p=r;

}

}
cleanUpVisit();
}

public void reversePreOrderTraversal()
{
printLRArray();
int p=1;
Stack stack=new Stack();
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
visit(p);
stack.push(p);
if(R[p-1]!=0)
p=R[p-1];
else
{
visit(R[p-1]);
p=L[p-1];
if(p==0)
visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{

r=L[stack.peek()-1];
if(r==0)
visit(r);
}
else
r=0;

}while(!stack.isEmpty()&& q==r);
p=r;

}

}
cleanUpVisit();
}
private Integer getIntegerFromBinaryString(String str,int i)
{
if(str.charAt(i)==’0’||str.charAt(i)==’)’)
return new Integer(0);
return new Integer(1);
}
/**
* Extra Credit
Write and test a program “create”, that reads the sequence of n 0’s and n 1’s (i.e. the n right and n left parentheses) representing an n node
binary tree as we discussed in class and creates a linked representation of the tree in memory using L and R. This program should echo the
input. After the tree is created, preorder traverse the tree, and as each node is visited, output its number and that of its left and right
successors.
Provide the actual output for a number of sample trees.
* @param binaryString
*/
public void createTree(String binaryString)
{
L=new int[binaryString.length()/2];
R=new int[binaryString.length()/2];
for(int i=0;i<L.length;i++)
{
L[i]=R[i]=-1;
}
int p=1;
Stack stack=new Stack();
int i=0;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(0)))
{
p=0;
for(int j=0;j<L.length;j++)
{
L[j]=R[j]=0;
}
}
int elementCount=2;
while(p!=0||!stack.isEmpty())
{

if(p!=0)
{
//visit(p);
i++;
stack.push(p);
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
L[p-1]=elementCount++;
else
L[p-1]=0;

if(L[p-1]!=0)
p=L[p-1];
else
{
i++;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
R[p-1]=elementCount++;
else
R[p-1]=0;
// visit(L[p-1]);
p=R[p-1];
// if(p==0)
// visit(p);
}
}
else
{
int q=0;
int r=0;
do
{
q=stack.pop();
if(!stack.isEmpty())
{
r=R[stack.peek()-1];
if(r==-1)
{
i++;
if(getIntegerFromBinaryString(binaryString, i).equals(new Integer(1)))
R[stack.peek()-1]=elementCount++;
else
R[stack.peek()-1]=0;
r=R[stack.peek()-1];
}

}
else
r=0;
}while(!stack.isEmpty()&& q==r);
p=r;

}

}
}

public static void main(String args[])
{
int L[]={2,0,0,0};
int R[]={4,3,0,0};

BinaryTreeInLRArray binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“110100100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“111000100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101100100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101010100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“101010100”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“111100000”);
System.out.println();
binaryTree.preOrderTraversal();

binaryTree=new BinaryTreeInLRArray(L,R);
binaryTree.createTree(“011100000”);
System.out.println();
binaryTree.preOrderTraversal();
}
}