Sign in to follow this  
Julian Spillane

Question About Tree Counting...

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 this post


Link to post
Share on other sites
Andrew Russell    1394
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this