• ### What is your GameDev Story?

This topic is 4983 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey all. I've been working on a commissioned project that involves finding the longest possible chain of dominos out of a hand, and choosing the best one (for someone's domino game AI). Now, after many trials and tribulations, I decided that the best way to do this would be to sort all of the data in a tree. i.e. Root: (0, 1) (1,2) (1,4)(1,6) (2,3) etc. Now, I've got it storing in the tree just fine, and I know my basic traversal algorithms, but for some reason...maybe it's the fact that it's 3:00 am, I can't figure out something for the life of me: How would I count the number of elements in a branch of the tree? Using the example above, the best chain would obviously be (0,1)-(1,2)-(2,3). But how would I go about counting that? I can't very well do it recursively, or I'd get the other guys. But if I don't do it recursively, I don't know how many levels exist in the tree. I considered a preorder traversal and then adding, but if a node has multiple children, it will count all of them. Do you guys have any suggestions? I hope I haven't been too ambiguous. Thanks a lot.

##### Share on other sites
Find the total number of nodes leading to each leaf node (or just for each node) by traversing the tree recusrivly. Store the length to that point in each node. Then just look for the leaf node that has the longest length by checking each node in the tree.

Go back up the tree from there and you have your chain.

Not necessaraly the fastest solution, but it will work.

Quote:
 I can't very well do it recursively, or I'd get the other guys. But if I don't do it recursively, I don't know how many levels exist in the tree.

Perhaps it's because you're tired - this dosn't make sense [smile].

##### Share on other sites
Thanks, Andrew.

Man...I was tired. Your advice seems quite sound, and I'll get to work on it right away and hope that I'll be able to overcome this early morning delirium enough to do it without any hassle. :p

Thanks a lot.

##### Share on other sites
Actually, I do have a question:

How would I find the number of nodes leading to each leaf node recursively?
I mean, if I had my tree set up like the example below, if I used a preorder traversal I'd get 1 + 2+ 4 + 5, and 3+6 as two separate pathways.

(1)
(2)(3)
(4)(5) (6)

If I went postorder, I'd get 4+5+2+1+6+3.
And there's no point in even considering breadth and inorder traversals for this.

I'm still not sure how I'd go about counting specific pathways.

Sorry to be a bother.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 12
• 15
• 11
• 12
• ### Forum Statistics

• Total Topics
634153
• Total Posts
3015844
×