How can you find all the paths that connect every pair of node on a binary tree?

Question

A few days ago, I got on my first hackathon (highly recommended to everyone) and for two of the seven problems you needed to find all the individual paths on a binary tree in order to process some data. But the real challenge for me was efficiently getting all the paths from the tree. I did a program on Java in order to take advantage of the containers found in its Standard Library. You can find my code here:
https://code.sololearn.com/cIs0rZa371we/?ref=app
So, how this task can be done more efficiently?

Answer 1

http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

https://en.m.wikipedia.org/wiki/Tree_traversal

Answer 2

@Nelson Hmm, the last time I did path tracing was for an airport/flight program, we we had to get all the possible flight paths from one destination to another. We used stacks with nodes such as:

struct node
{
char dest1;
char dest2;
};

wherein dest1 stores the origin and dest2 stores the next destination. Backtracking. Not sure how that compares to "all paths in a binary tree". It should be easier though, I'll try to code a sample later.

Answer 3

This is a little something that I have come up with, but after referencing to your code, it seems like it may not be what you want. (?) Nonetheless, I'll just post it here.

https://code.sololearn.com/chpa5lTMibya/?ref=app

Answer 4

@hatsy link mode on XD

else
from my own experience, working with linked lists in trees is a bit off in terms of efficiency

don't take it bad but get a good book on algorithm implementation in java

all these things are discussed in details and it will help you in upcoming competitions !

Answer 5

sorry i meant algorithm above

Answer 6

@hatsy I don't believe that the fun part of the challenge is the tree transversal. As you can see on my code, I tried a BSF to transverse the tree. But how you build and register all the possible paths that connects each already visited node with the new visited node while you traverse the tree?... and how to do it efficiently...

@Abdur-Rahmaan That's pretty interesting... I used linked list based on a book that I read on college (Network Flows Theory, Algorithms and Applications) which mentioned the advantage on linked list in terms of efficiency when dealing with trees. But I have seen some other people code where they don't use it at all, not any other collection from the standard library. I will take your word and try to rewrite the algorithm without the linked list and compare the execution time. Thanks for your advice!!

Answer 7

@hatsy Thanks for your last post. I will take some ideas from that code but you are right... it's not exactly what the challenge asked. Mainly for two reasons: First your posted code build an ordered binary-tree from the input and in the challenge it could be any kind of binary tree (order doesn't matter)... second, the code only finds the paths from the root to each other node, but we need to find the path to every single pair of nodes and that means that you need to repeat the process starting from every single node in the tree... but there is a catch... if you start from a leaf node, how do you know which node is upside the tree if you only has the left and right children address of that node in the datastructure? Probably, you will have to register the parent node address also and make some changes to the code, but maybe it can work. I will try to impplement it and post it here later.