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?

Solution 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/

Solution 2

Check the answer given by Niki in the following link.. That is O(n) solution

Diameter of Binary Tree - Better Design

Comments

[Raptor]

sounds like a homework / assignment .

[Gene]

You need to define "path". Do you mean root-to-leaf path? Or do you mean the longest path from some leaf to any other leaf? There's a big difference.

[Majid Darabi]

@Vinay: Diameter of a tree is the longest path!

[vladon]

@MajidDarabi path in a tree - is a contiguous nodes sequence, that can be traversed only using pointers (to left and right leaves), diameter is not a path!

[Majid Darabi]

@VladislavYaroslavlev Could you add a reference to your definition of a path in a tree?? (a scientific paper or a book) because based on the general definition of a path in a graph, I could not conclude your definition. en.wikipedia.org/wiki/Path_%28graph_theory%29