CODEWITHSUNDEEP
algorithmsearchrecursiontree
SRobertJames
SRobertJames

Reputation: 9206

Determining if a tree walk is breadth first, depth first, or neither

Given a tree T and a sequence of nodes S, with the only constraint on S being that it's done through some type of recursion - that is, a node can only appear in S if all of its ancestors have already appeared, what's a good algorithm to determine if S is a breadth first visit, a depth first visit, or neither?

A brute force approach is to compute every breadth first and depth first sequences and see if any is identical to S. Is there a better approach?

What if we don't want a yes or no answer, but a measure of distance?

UPDATE 1 By measure of distance, I mean that a visit may not be an exact BFS, but it's close (a few edits might make it one); I'd like to be able to order them and say BFS < S < R < U < DFS.

UPDATE 2 Of course, a brute force enumeration of every BFS or DFS can answer the question; I'd like something more efficient.

Upvotes: 2

Views: 348

Answers (1)

ElKamina
ElKamina

Reputation: 7807

You have the tree and the sequence, right? In that case it is pretty easy to determine if a sequence is breadth first search or not, and if it is depth first or not.

To check if it is breadth first: divide the nodes into groups L0, L1, ..., Lk where L0 is the set of 0 level nodes (there is only one root node, so its size is 1), L2 is the set of level 1 nodes and so on. If sequence S = (permutation(L0), permutation(1), ...) then it is a breadth first search.

To check if it is depth first: start with a pointer to the first node in the sequence and root node of the tree. They should be same. Next element of the sequence must be a child of previous node, if the previous node has any children at all. If there is a conflict then it is not a DFS sequence. If there is no child, then the next sequence element must be child of parent of previous node,... and so on. This approach is not as complicated as it sounds and could be easily implemented with the help of a stack.

I am not very sure for your need for "measure of distance". But as you can see, both of these approaches can return number of conflicts. Maybe you can use it to calculate "distance"?

Upvotes: 1

Related Questions