How to create a linked list of nodes that are contained in the max-Depth of a Binary Tree using Java

Question

I've already created the Binary Tree and Linked list classes, I'm just in need of an algorithm that prints ONLY the nodes of the largest path. The height and size of the Binary Tree are already stored in the root node, but my problem is traversing only the largest path while adding each node to my linked list.

Answer 1

I assume your binary tree nodes have a reference to their parent, is that right? Then you could use either a breadth-first search or a depth-first search and find root nodes where the depth is equal to the max depth. Once you find one such node, then from there go up the trail of parent nodes, and add each node along the way to your linked list. When you reach the top, then the linked list has all the nodes of the largest path.

This algorithm would look like this:

1. start at the root of the binary tree
2. use a breadth-first or depth-first search to reach leaf nodes (nodes which do not have any children nodes)
   1. when you reach a leaf node, check it's depth:
      1. if it's not equal to the max depth, ignore it and continue with the search
      2. if it's equal to the max depth, then you've found the end node of a largest path (there could be more than one but it doesn't seem important to distinguish them at this point). go to the next step
3. add this leaf node to the linked list, then go to it's parent
4. repeat that last step until you reach the root node and there is no parent - then your linked list has all the nodes of a longest path.

Note that the order of the nodes is from the leaf node to the root - if you need to reverse it, you can do so after the last step.