Find diameter for any tree

The diameter of a tree is the maximum length of path between any vertex in a tree. The simple solution is to start from any vertex, do a DFS, find a farthest vertex from it, then from that farthest vertex, do second DFS, find the farthest vertex from it.

//here is the graph node with adjacentList representation.
//for illustration purpose, the key of each vertex is character

public static class CNode {

char c;

Set<CNode> outgoing = new HashSet<CNode>();

CNode(char i){this.c=i;}

        public int hashCode() {}

        public boolean equals(Object o){}

}

public static int diameterOfTree(CNode[] vertices){

int[] max = new int[1];

CNode[] mNode = new CNode[1];

Set<CNode> visited = new HashSet<CNode>();

//start with any vertex in the tree

dfs(vertices[0], 0, visited, max, mNode);

CNode[] maxNode = new CNode[1];

max[0] = 0;

visited = new HashSet<CNode>();

dfs(mNode[0], 0, visited, max, maxNode);

return max[0];

}

public static void dfs(CNode start, int distance, Set<CNode> visited, int[] max, CNode[] maxNode){

visited.add(start);

max[0] = Math.max(max[0], distance);

if(max[0]==distance)

   maxNode[0] = start;

for(CNode n : start.outgoing){

if(!visited.contains(n)){

dfs(n, distance+1, visited, max, maxNode);

}

}

}

Convert Binary Search Tree to Sorted Doubly-linked list

This is very interesting problem. And most of solutions are recursive approach which will cause stack overflow.

The below is my solution, which does in-place and iteratively.

The idea is to in-order traverse the tree and use head pointer referencing the head of the linked list and pre pointers referencing the previous node during traverse.

public static Node isBSTAndTreeToDLL(Node root){

if(root==null)

return null;

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

Node head = null;

Node n = root;

Node pre = null;

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

if(n!=null){

s.push(n);

n = n.left;

}

else{

Node p = s.pop();

//this is the left most node

if(head == null)

head = p;

if(pre!=null){

pre.right = p;

p.left = pre;

}

pre=p;

n = p.right;

}

}

//handle the last node

pre.right = head;

head.left = pre;

return head;

}