Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

walk_tree_bfs doesn not implement BFS #72

Open
qheath opened this issue Jan 3, 2018 · 0 comments
Open

walk_tree_bfs doesn not implement BFS #72

qheath opened this issue Jan 3, 2018 · 0 comments

Comments

@qheath
Copy link

qheath commented Jan 3, 2018

the current implementation of walk_tree_bfs actually implements DFS, as evidenced by the fact that it is almost identical to walk_tree_dfs

in other words, walk_tree_bfs node {...} is identical to walk_tree_dfs node { |node,level| node.children.each { |child| ... }}, modulo some corner-cases

I think the tests used in test/acts_as_tree_test.rb are not deep enough to show the difference, but if you take

1
-2
--3
---4
-5
--6
---7

then the current implementation generate

1 2 5 3 4 6 7

while I believe true BFS would generate

1 2 5 3 6 4 7

(4 and 6 are switched)

a correct implementation should use a FIFO to keep tracks of the next generation; I will suggest one later, unless someone beats me to it or explains that I'm mistaken

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant