0

I know there are lots of questions on here dealing with Breadth First Search vs Depth First Search, but I think that my situation is a little different.

I have a rooted tree in which each node may have 0, 1 or 2 children (with the expected number being 1). Given a large number n, I want to find a path through the tree of length n.

It seems clear that depth-first should be the best way to do this, but I'm not so sure. The width of the tree is very small, which is normally a reason to use breadth first search. In addition, if I use depth first search, then I could end up following going down into a subtree whose height is very close to n, but smaller than n. In that case, I will waste a lot of time traversing a tree that can't possibly give me the answer I want

John Gowers
  • 2,646
  • 2
  • 24
  • 37
  • 2
    I would suggest you look at iterative deepening depth first search. – Rudrani Angira Aug 30 '17 at 16:31
  • you might wanna look at https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-dfs-vs-bfs – marvel308 Aug 30 '17 at 16:31
  • @marvel308 I have, and I have referred to what I found out there in the question. – John Gowers Aug 30 '17 at 16:41
  • @RudraniAngira Isn't that worse than depth first search? In order to find a node at depth `n`, I have to search the entire tree up to depth `n-1`. A depth first search would certainly be preferable to that. – John Gowers Aug 30 '17 at 16:43
  • @JohnGowers IDDFS would stop at the depth where your goal state would be. – Rudrani Angira Aug 30 '17 at 16:44
  • @RudraniAngira Yes it would, but before it did that it would have to search through much more of the tree than a simple depth-first search would. – John Gowers Aug 30 '17 at 17:12
  • You say you want to find **a** path. Is this a one-time query, or are you going to need to find multiple paths (with possibly different values of `n`) in the same tree? If this is a one-time thing, since the worst-case performance of the two searches is the same, I would suggest you compare the best-case performance. – beaker Aug 30 '17 at 21:19
  • This is a one time query. I think you're right, though: with depth first search, there's a chance that we have to search through more of the tree than we want to. But with breadth first search, that happens all the time. – John Gowers Aug 30 '17 at 22:06
  • With no extra information of the tree, assuming it has no special ordering or structure, I do not think you can do better than O(M) where M is the # of nodes of the tree and M > n. If the construction of the tree can be modified, then you may store the height of the subtree rooted at a node when building the tree, then you can achieve O(n) easily in this one time query. – shole Aug 31 '17 at 01:45

1 Answers1

1

  1. DFS will always be more efficient than BFS for your goal. since BFS iterate over all nodes in depth 1, then all the nodes in depth 2, and so on, in order to find a path of length n, BFS will first travel through all paths in the tree of length <= n-1. in the absolute worst case, DFS will do the same until finding the requested path, but in the general case, DFS will be far more efficiently in my opinion.

  2. I know that's not always possible, but of you can change your tree implementation so that every node will contain the length of it's sub-tree (the max value between the node's children), it'll will solve your problem and is very easy to maintain during regular insert\remove etc.

sicarii443
  • 51
  • 5