longest repeated substring using simplest suffix tree

public class SuffixTree {

STNode root;

class STNode {

int data ;

STNode[] edges;

STNode(int d){

data = d;

}

STNode(){

}

}

//assume small cases: a-z

STNode addString(String s, int data){

if(root==null)

root = new STNode(-1);

STNode current = root;

int index = 0;

while(index<s.length()){

if(current.edges==null)

current.edges = new STNode[26];

int pos = s.charAt(index) - 'a';

if(current.edges[pos]==null)

current.edges[pos] = new STNode();

current = current.edges[pos];

index++;

}

current.data = data; //leaf store the position

return root;

}

public void addAllSubString(String s){

for(int i=0;i<s.length();i++){

this.addString(s.substring(i), i);

}

}

public String findLongestRepeatSub(String s){

this.addAllSubString(s);

Deque<STNode> sk = new ArrayDeque<STNode>();

sk.add(root);

int maxL = 0;

int currentL = 0;

STNode target = root;

while(!sk.isEmpty()){

Deque<STNode> temp = new ArrayDeque<STNode>();

while(!sk.isEmpty()){

STNode n = sk.remove();

currentL++;

int counter=0;

if(n.edges!=null){

for(STNode nd : n.edges){

if(nd!=null){

sk.add(nd);

counter++;

}

}

}

if(counter>1 || counter==1 && n.data>0){

if(currentL>maxL){

maxL = currentL;

target = n;

}

}

}

sk = temp;

}

int cn = 0;

//go down to the leaf if not on leaf yet.

while(target.data<=0){

if(target.edges!=null){

for(STNode nd : target.edges){

if(nd!=null){

target = nd;

cn++;

}

}

}

}

if(cn!=0)

return s.substring(target.data, s.length()-cn+1);

else

return s.substring(target.data, s.length());

}

}

In-Order Flatten A Binary Tree to Linked List

In-order flatten binary tree, the idea here is similar to in-order traverse of the tree, keep a pointer to previous node visited, then link current node with previous.

public static void FlattenABinaryTreetoLinkedListInOrder(Node root){

Stack<Node> s = new Stack<Node>();

Node c = root;

Node pre = null;

while(!s.isEmpty()||c!=null){

if(c!=null){

s.push(c);

c = c.left;

}

else{

Node n = s.pop();

if(pre!=null){

pre.right = n;

pre.left = null;

}

pre = n;

n = n.right;

}

}

}

Pre-Order Flatten A Binary Tree to Linked List

To do it iteratively is little bit tricky, since when we do down to the left of tree, we need to remember the way to go back to right.

The idea is to use a stack to store the right child when we go to left.

Here is the code:

public static void FlattenABinaryTreetoLinkedList(Node root){

Stack<Node> s = new Stack<Node>();

Node c = root;

while(!s.isEmpty()||c!=null){

if(c.left!=null){//keep on going left

if(c.right!=null)//remember the right child

s.push(c.right);

c.right = c.left;

c.left = null;

c = c.right;

}

else{//reach the far left, now we need to go right

Node n = s.pop();

c.right = n;

c = n;

}

}

}