## Praveen Ram C

BAN USERWorking towards my Graduate degree in Computer Science at University of Texas at Dallas.

Comments (2)

Reputation 20

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

I don't really thing you need to do a level order traversal for this. Though at the first glance at the problem, you might be tempted to use. We can create a array of size equal to the depth of the tree to store all the path from root to leaf. Whenever we hit the leaf node, the array will contain the path from root to leaf. Then you have to do a simple comparsion operation to get maximum sequence count.

```
private int depth(Node root) {
if(root == null) return 0;
else return 1 + Math.max(depth(root.leftChild), depth(root.rightChild));
}
public int maxSequence() {
int depth = depth();
int[] path = new int[depth];
return maxSequence(root, path, 0);
}
private int maxSequence(Node node, int[] path, int level) {
if(node == null) {
return getSequenceLength(path, level);
}
path[level] = node.element;
return Math.max(maxSequence(node.leftChild, path, level+1),
maxSequence(node.rightChild, path, level+1));
}
private int getSequenceLength(int[] path, int level) {
int count = 1;
int depth = 0;
while(depth < level) {
for(int index = 0; index < level-1; index++) {
if(path[index] < path[index+1]) {
count++;
} else {
depth = index + 1;
}
}
return count;
}
return count;
}
```

I'm not sure if the code can be optimized any further.

- Praveen Ram C March 10, 2015Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Can be modeled as a graph problem. Let the vertex be the set of all words that are given to us, including the start and end words.

- Praveen Ram C June 23, 2015Now, for each vertex, there exists an edge if a vertex can be converted to another vertex.

So, lets say we have "dog" and "cog". Since dog can be converted to cog by replacing one character, we ad an edge between them.

Once we are done constructing the graph, all we have to do is do a BFS between the start node and end node which also gives us the shortest path.