Finding the Longest Path in a Binary Tree

Question

I want to find the longest path in a Binary Tree. I plan to add them to a list, that way I can tell my enemy character to take the long path on easy mode.

private static <T> ArrayList<T> depthFirstSearch(BinaryNode<T> node)
{
    if(node != null)
    {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();

        stack.push(node);

        while(!stack.isEmpty())
        {
            BinaryNode<T> currentNode = stack.pop();



            if(currentNode.right != null)
                stack.push(currentNode.right);

            // We want to visit left child first, so push left node last.
            if(currentNode.left != null) 
                stack.push(currentNode.left);
        }
    }
}

I have written that code, but it is a mess. I am trying to use DFS to find the longest path to take. Any suggestions?

EDIT: I do have the height of the tree, I can get it using this.

public static <T> int height(BinaryNode<T> t)
{
    if (t == null)
        return -1;

    else 
        return 1 + Math.max(height(t.left), height(t.right));
}

My issue is: when do I know that I have found the longest path using DFS so that I can add nodes to my list?

Answer 1

The longest path in a tree, is called "diameter". You can see the implementation of the algorithm here: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/