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

Well make a binary tree data structure, fill it with some dummy data, traverse the tree with a depth or breadth first search and construct a linked list of the nodes in the longest path.

There's plenty of pseudo code and further information online:

http://en.wikipedia.org/wiki/Binary%5Ftree

http://en.wikipedia.org/wiki/Linked%5Flist

http://en.wikipedia.org/wiki/Breadth-first%5Fsearch

http://en.wikipedia.org/wiki/Depth-first%5Fsearch

I assume you already understand Java and are not starting completely from scratch?

If you're struggling with Java then Objects First with Java is a great book and also Introduction to Algorithms seems to be the standard book on algorithms and may be well worth looking at.

Answer 2

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.