Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Diameter of Binary Tree - Better Design

I have written a code for finding diameter of Binary Tree. Need suggestions for the following:

  1. Can I do this without using static variable at class level?
  2. Is the algorithm fine/any suggestions?

    public class DiameterOfTree {   
    public static int diameter = 0; 
    public static int getDiameter(BinaryTreeNode root) {        
        if (root != null) {                     
            int leftCount = getDiameter(root.getLeft());
            int rightCount = getDiameter(root.getRight());
            if (leftCount + rightCount > diameter) {
                diameter = leftCount + rightCount;
                System.out.println("---diameter------------->" + diameter);
            }           
            if ( leftCount > rightCount) {
                return leftCount + 1;
            }
            return rightCount + 1;
        }
        return 0;
      }
    }
    
like image 753
Manish Avatar asked Aug 10 '12 07:08

Manish


People also ask

In what time complexity can we find the diameter of binary tree optimally?

Finally, the diameter is maximum among all maximum node paths for every node in the tree. The time complexity of this solution is O(n2) as there are n nodes in the tree, and for every node, we are calculating the height of its left and right subtree that takes O(n) time.

What is the diameter of a binary tree?

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root . The length of a path between two nodes is represented by the number of edges between them.

In what time complexity can we find the diameter of a binary tree optimally O v e O v O'e O v * loge?

In what time complexity can we find the diameter of a binary tree optimally? Answer - A) We can compute the diameter of a binary tree using a single DFS, which takes the time of O(V + E). 7.

What is the best case height of a binary search tree?

If there are n nodes in a binary search tree, maximum height of the binary search tree is n-1 and minimum height is ceil(log2(n+1))-1.


2 Answers

There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):

  1. The longest path passes through the root,
  2. The longest path is entirely contained in the left sub-tree,
  3. The longest path is entirely contained in the right sub-tree.

The longest path through the root is simply the sum of the heights of the left and right sub-trees (+1 for the root not necessary since the diameter of a tree with a root node and 1 left, 1 right subtree nodes will be 2), and the other two can be found recursively:

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()); //Removing the +1
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public static int getHeight(BinaryTreeNode root) {
    if (root == null)
        return 0;

    return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
}
like image 140
verdesmarald Avatar answered Oct 06 '22 01:10

verdesmarald


Here is an O(n) solution with minimal changes to the accepted answer:

public static int[] getDiameter(BinaryTreeNode root) {
    int[] result = new int[]{0,0};    //1st element: diameter, 2nd: height    
    if (root == null)  return result;
    int[] leftResult = getDiameter(root.getLeft());
    int[] rightResult = getDiameter(root.getRight());
    int height = Math.max(leftResult[1], rightResult[1]) + 1;
    int rootDiameter = leftResult[1] + rightResult[1] + 1;
    int leftDiameter = leftResult[0];
    int rightDiameter = rightResult[0];
    result[0] = Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
    result[1] = height;

    return result;
}

It just calculates height and diameter at the same time. And since Java does not have pass-by-reference I defined an int[] to return the result.

like image 27
Niki Avatar answered Oct 06 '22 01:10

Niki