## rathi

BAN USER
Comments (3)

Reputation 0

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

One can modify the BFS algorithm ..

BFS(source)

{

set discovered[source] = true;

int i = 0;

Initialise list l[0] with s

while( l[i] not empty)

{

initialise l[i+1]

get element := from l[i];

for each node adjacent to element

{

if discovered[node] == false

{add to l[i+1]

set discovered[node] = true

}

else

{if discovered [node] == true // node already been prevously detected therefore cycle !

print("cycle");

return

}

}

i =i +1

}

}

Comment hidden because of low score. Click to expand.

Page:

1

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

If the given tree is a BST then the second solution posted above is right. But since it has just been provided as a Binary tree i dont think we can use that solution.

- rathi December 04, 2007@Laks: Inorder traversal is just a method of printing out nodes, since we can assume the Binary tree to be ordered in any particular manner.. i dont think simply doing a inorder traversal would give the result.

A brute force approach i can think of ;)

- Do a traversal and store the values of all nodes in an array - O(n)

- Find the next higher element by making a one pass through the array-

O(n)

Val : = value of node given to us .. whose higher noder we have to find

Big : value of the next bigger node set to 0

for( i from 1 to n)

{

if (array[i] > Val)

{

if(array[i] < Big)

Big = array[i]

}

}

- Traverse the tree looking for the node having the value of Big and return O(n)

Maybe the whole thing can be accomplished by 2 Traversals too minus the temp array

Do a traversal and find value of Big

Do a traversal and get node corresponding to Big