Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Consider a particular "node":- we have three cases
1. Longest Possible path includes node->left and not this node
2. Longest Possible path includes node->right and not his node
3. Longest Possible path includes this "node"

Thus, longest possible path should be maximum of these three: (node->left, node->right, 1+height(node->left) + height(node->right))

OutPut

H
D
B
A
H
D
B
diamater7

Java Code

import java.util.ArrayList;
import java.util.List;

public class longestPathInTree {
    // node class
    class node {
        node right;
        String val;
        node left;

        public String getVal() {
            return val;
        }

        public void setVal(String val) {
            this.val = val;
        }

        public node getRight() {
            return right;
        }

        public void setRight(node right) {
            this.right = right;
        }

        public node getLeft() {
            return left;
        }

        public void setLeft(node left) {
            this.left = left;
        }

        public node(String val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        longestPathInTree path = new longestPathInTree();
        path.find();
    }

    public void find() {
        node root = new node("A");
        node b = new node("B");
        node c = new node("C");
        node d = new node("D");
        node e = new node("E");
        node f = new node("F");
        node g = new node("G");
        node h = new node("H");
        node i = new node("I");
        node j = new node("J");
        node k = new node("K");
        node l = new node("L");
        node m = new node("M");
        node n = new node("N");
        root.setLeft(b);
        root.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);
        c.setRight(g);
        d.setLeft(h);
        d.setRight(i);
        e.setLeft(j);
        e.setRight(k);
        f.setRight(l);
        f.setLeft(m);
        g.setLeft(n);

        int diameter = 0;
        List<node> leftPath = findLongestPath(root.getLeft());
        diameter = diameter + leftPath.size();
        for (int z = leftPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println(root.getVal());
        List<node> rightPath = findLongestPath(root.getRight());
        diameter += rightPath.size();
        for (int z = rightPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println("diamater: " + ++diameter);

    }

    /**
     * if node does not have child node, then it will be child node else move
     * inside
     *
     * @param n
     * @return
     */
    private List<node> findLongestPath(node n) {
        List<node> stacks = new ArrayList<node>();
        node left = n.getLeft();
        node right = n.getRight();
        stacks.add(n);
        if (left == null && right == null) {
            return stacks;
        } else {
            List<node> sl = new ArrayList<longestPathInTree.node>();
            List<node> sr = new ArrayList<longestPathInTree.node>();
            if (left != null) {
                // Find longest path to left of node.
                sl = findLongestPath(left);
            }
            if (right != null) {
                // Find longest path to right of node.
                sr = findLongestPath(right);
            }
            if (sl.size() >= sr.size()) {
                for (node e : sl) {
                    stacks.add(e);
                }
            } else {
                for (node e : sr) {
                    stacks.add(e);
                }
            }
            return stacks;
        }
    }
}