Loop In a Binary Tree

[Amar Kumar Dubedy]

If there is a loop in a Binary Tree(or a BST) then how would u detect
it and remove it??

[Dave]

This is a contradictory question, since by definition, a tree cannot
have a cycle.

E.g., from http://en.wikipedia.org/wiki/Tree_(graph_theory)

Definitions: A tree is an undirected simple graph G that satisfies any
of the following equivalent conditions:

G is connected and has no simple cycles.
G has no simple cycles, and a simple cycle is formed if any edge is
added to G.
G is connected, and it is not connected anymore if any edge is removed
from G.
G is connected and the 3-vertex complete graph K3 is not a minor of
G.
Any two vertices in G can be connected by a unique simple path.

Dave

[Amar Kumar Dubedy]

what if u r given a root node of a binary tree(or a BST) such tht one
of the leaf nodes point to an internal node? I know it will not remain
a binary tree nymore if there is a loop. But if u intend to remove the
loop nd make it a binary tree then how wud u proceed??

[Dave]

So you are asking, "How you can convert a connected graph into a
tree?"?

This is simple. Traverse the graph, marking each node as you visit it.
If an edge from the current node connects to a marked node, delete the
edge.

Dave

[Prashanth Mohan]

Dave wrote:
> This is simple. Traverse the graph, marking each node as you visit it.

This would require that a flag be added to each node. Is there a way to
do it without modifying the Data Structure?

--
Prashanth Mohan
http://prashblog.com

[Praveen]

I have one strategy.

I am not sure about the whcih language you use for coding

Steps:
1. Implement a recursive function which traverse the BST (the left
child and right child) it could be any thing like inorder, or
preorder
2. Once you visit a node strore the current node, and corrupt that
node at each visit
3. When the loop occurs, you can not access that node ... it may
through some exception(because you already visited that node and you
currupted it).
4. Remove that loop pointer.
5. Recursively construct the corrupted nodes.

I think this is a stupid logic........ ; )

Thanks,
Praveen.

[Dave]

A tree with n nodes has n-1 edges. So if you know how many nodes the
graph has, you can traverse the tree, counting the edges as you go. If
you get to edge n, you know it is not a tree. Therefore, it must be a
graph with a cycle. I haven't figured out how to decide which edge(s)
to remove to reduce the graph to a tree.

Dave

[Gowri Kumar CH]

Hi Praveen,
I think for a BST (Binary Search Tree) we might use your logic with a
slight modification.
In a BST, an inorder traversal results in a sorted list of the
numbers. So, as we are doing the inorder traversal on the BST, if the
current node value is less than the previous node value, then that's
probably a place where the cycle is.

Regards,
Gowri Kumar

[Usman Ahmad]

Gowri!

Your solution seems good. but what if root is pointing to itself? / or what if all nodes in BST has same number. {2,2,2,2,2,2,2,2} . how will you then decide?

 

Preveen!

 your solution is great. but what if you are at lowest level in tree and next node in BST is null? which is valid in normal BSTs.

 

-Usman

 

[Gowri Kumar CH]

Hi Usman,
But I have always seen/implemented the BST to not to have duplicates
in the tree.
- Either you don't insert the duplicates in the tree
- Or Maintain a count of number of times the values exist.

Hence the solution might work.

OTOH, how do you insert duplicate values into BST?
In particular, if the node value is the same, do you insert to the
left or right?

Regards,
Gowri Kumar

[Usman Ahmad]

Gowri,

 

Your solution is right. I was wrong.

 

Regards,

Usman Ahmad