CareerCup

Graph has Vertices and Edges, I am not sure what they mean by leaf node in a Graph. What does it mean? Can some one calrify what exactly the question is?

why it is a graph, sounds like a tree.

what do u mean by Starting Node and Ending Node in a Graph?

To find the path, start at the end and work your way back (since each node only has one parent) if the start node is not found fail.

Now then, how do you define "Finding a leaf node"?

1) If a finding a leaf node means finding a node with "no children" on the path, then the only possible leaf node on the path from start point to end point (inclusive) is the end point, and only if the end point has no children.

2) if a finding a leaf node means finding a node that has childless children, then, as you traverse back, check all children of each node in the path to see if any are childless

3) if finding a leaf node means finding each childles child of each node in the path, then, as you travers back, check all children of each node and count how many have no children themselves.

Union DFS (start node) with DFS (end node)? While DFS from start node, insert all nodes into a hashtable, and when searching from end node, do not traverse nodes already in the hashtable.

I think this is recursive. If found end node. press teh boolean button for the parent. Add at the end to whatever state keeping structure you have. When you recourse back, rinse, up to the top.

When you call your boolean should always be false. It is only when you return that it can become true.

Do the level order traversal of the given tree (graph) from the starting node to the end node and record all the nodes with no children.

I am assuming that when we traverse from starting node to the ending node, we should record all the intermediate leaf nodes (if encountered any ).

BFS aka Level order traversal should work.

Preorder traverse the tree and annotate each node with the enter time and leave time, the difference between leave time and enter time of the leaf node is one. (time start at one and metric is one).

I think this is actually a graph with a source and sink. There can be leaf nodes in between which have no child nodes. End node is a special leaf node.

Assuming the graph is a binary tree :

boolean populateList(Node root, LinkedList<Node> list, Node start, Node end) {
		if (root != null) {
			if (root.left == null && root.right == null)
			{
				if (root == start) 
					list = new LinkedList<Node>();
				if (list != null)
					list.add(root);
				if (root == end)
					return true;
			}
			else {
				if (populateList(root.left, list, start, end))
					return true;
				if (root == start)
					list = new LinkedList<Node>();
				if (root == end)
					return true;
				return populateList(root.right, list, start, end);
			}
		}

		return false;
	}

Node start;
Node end;
printAllLeaf(Node e)
{
   if(e==null) return;
   else{
       ArrayList<Nodes> children = e.getChildern();
       for(Node child :children)
       {
           if(child.getChildren().size()==0)
               visit(child);
       } 
       printAllLeaf(e.parent);     
   }
}