Diameter of Binary Tree - Better Design

Question

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

Can I do this without using static variable at class level?

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;
  }
}

what do you mean by is the algorithm fine?. Did you test the code? — arunmoezhi
– arunmoezhi, Commented Aug 10, 2012 at 7:23
arun, offcourse i have tested the code. I mean can there be a better algorithm? — Manish
– Manish, Commented Aug 10, 2012 at 7:24
@Barth, thanks. Didnt know about code review. Will try there as well. — Manish
– Manish, Commented Aug 10, 2012 at 7:33
@Manish Ohh ok. Please refer to this geeksforgeeks.org/archives/5687 — arunmoezhi
– arunmoezhi, Commented Aug 10, 2012 at 7:33

Vrashabh Irde · Accepted Answer · 2020-04-30 12:03:02Z

42

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

The longest path passes through the root,
The longest path is entirely contained in the left sub-tree,
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;
}

edited Apr 30, 2020 at 12:03

Vrashabh Irde

14.4k8 gold badges54 silver badges106 bronze badges

answered Aug 10, 2012 at 7:49

verdesmarald

11.9k2 gold badges46 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

AKS Over a year ago

@Harshdeep, Yes it's complexity is O(n^2) as it travels every time till bottom to find the height. I am looking for code which calculates height in same traversal as diameter.

JavaDeveloper Over a year ago

You are mixing height with nodes, height is 'number of edges', so a tree with only single node has height of 0. technically your code is correct, but not in terminology.

kirakun Over a year ago

According to this code, the diameter of this tree: a -> b -> c -> d is 4. But the only leaf node is d. So, the diameter, which is defined as the length of the longest path between two leaves, should be 1.

unknown_boundaries Over a year ago

@kirakun, Should not the diameter be 0 (or length to root * 2) in this case?

Ermias K Over a year ago

rootDiameter, should be the sum of leftHeight and rightHeight. Because, the diameter of tree with only 2 node is 1. int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight());

Community · Accepted Answer · 2014-10-26 12:26:37Z

41

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.

edited Oct 26, 2014 at 12:26

CommunityBot

11 silver badge

answered Oct 1, 2013 at 17:51

Niki

1,1231 gold badge10 silver badges18 bronze badges

1 Comment

Patrizio Rullo Over a year ago

The line int[] rightResult = getDiameter(root.getLeft()); should probably be: int[] rightResult = getDiameter(root.getRight());?

nem035 · Accepted Answer · 2016-01-16 10:20:14Z

9

Here is a solution in Java that has O(N) time complexity. It calculates the height in the same recursion when calculating the diameter. Reference Link

private class HeightWrapper {
    int height = 0;
}

private int getDiameter_helper(BinaryTreeNode root, HeightWrapper wrapper) {
    if (root == null) {
        return 0; // diameter and height are 0
    }

    /* wrappers for heights of the left and right subtrees */
    HeightWrapper lhWrapper = new HeightWrapper();
    HeightWrapper rhWrapper = new HeightWrapper();

    /* get heights of left and right subtrees and their diameters */
    int leftDiameter = getDiameter_helper(root.left, lhWrapper);
    int rightDiameter = getDiameter_helper(root.right, rhWrapper);

    /* calculate root diameter */
    int rootDiameter = lhWrapper.height + rhWrapper.height + 1;

    /* calculate height of current node */
    wrapper.height = Math.max(lhWrapper.height, rhWrapper.height) + 1;

    /* calculate the diameter */
    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public int getDiameter(BinaryTreeNode root) {
    HeightWrapper wrapper = new HeightWrapper();
    return getDiameter_helper(root, wrapper);
}

edited Jan 16, 2016 at 10:20

answered Aug 27, 2014 at 0:42

nem035

35.5k6 gold badges93 silver badges104 bronze badges

4 Comments

Amarnath Over a year ago

+1 .. Thanks for the solution. Why should we keep them in a wrapper class? I have seen the link and I am not able to implement the same in Java. But your solution seems to be working fine. Can you edit the above answer and explan why we need a wrapper class?

nem035 Over a year ago

Hi @Che, the reason you need a wrapper class is because Java is Pass By Value meaning that using an object wrapper around your data is the easiest way to properly maintain values through recursion levels. Here is another useful link

Aditya Joshee Over a year ago

@nem035 : For a tree with only 1 node, your code will give 1 as the diameter which is wrong. It should be 0 for such a case.

nem035 Over a year ago

Well, 1 node is case for which you could argue both 0 or 1 could be valid answers. It all depends if, in your considered definition of the diameter, you count the starting node when you calculate it.

stakx - no longer contributing · Accepted Answer · 2012-08-10 09:22:33Z

4

You don't need to store the result in the static field diameter. Simply use the static method like that:

public class DiameterOfTree {

    public static long getDiameter(BinaryTreeNode root) {
        if (root != null) {
            long leftDiameter = getDiameter(root.getLeft());
            long rightDiameter = getDiameter(root.getRight());
            long leftHeight = getHeight(root.getLeft());
            long rightHeight = getHeight(root.getRight());
            return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
        }
        return 0;
    }

    public static long getHeight(BinaryTreeNode root) {
        if (root != null) {
            long leftHeight = getHeight(root.getLeft());
            long rightHeight = getHeight(root.getRight());
            return  1 + Math.max(leftHeight, rightHeight);
        }
        return 0;
    }
}

edited Aug 10, 2012 at 9:22

stakx - no longer contributing

85.1k20 gold badges176 silver badges277 bronze badges

answered Aug 10, 2012 at 7:39

Xavier Delamotte

3,60921 silver badges30 bronze badges

3 Comments

Keppil Over a year ago

This doesn't give you the diameter, it gives you the depth.

AKS Over a year ago

@Xavier Can you provide code for optimized version which calculates height in same recursion as diameter, so that it does not have to go till bottom to calculate the height? That way it's complexity will come down to O(n) from O(n^2)

rliu Over a year ago

@AKS You can trade time for space and add memoization for linear time complexity (because every node's height can be computed from the results of its subtrees in O(1) time). Alternatively, you can use one post-order traversal (which can be done iteratively instead of using recursion) and store those results.

roottraveller · Accepted Answer · 2017-08-24 10:41:54Z

3

There is a minimal O(n) answer compared to the accepted one.

int DiameterTree(BinaryTreeNode root, int diameter) {
    int left, right;
    if (!root) return 0;

    left  = DiameterTree(root.getLeft(), diameter);
    right = DiameterTree(root.getRight(), diameter);
    if (left + right > diameter) diameter = left + right;

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

Assume diameter is a static variable in class.

edited Aug 24, 2017 at 10:41

roottraveller

8,3108 gold badges65 silver badges70 bronze badges

answered Mar 15, 2015 at 2:58

shakirthow

1,35614 silver badges15 bronze badges

2 Comments

roottraveller Over a year ago

Why are you using diameter as normal variable in method argument?

Learner Over a year ago

Can you please explain this algorithm ? I'm not able to get the concept of adding 1 in the return statement ..

Snehal Masne · Accepted Answer · 2013-11-10 18:29:28Z

The diameter of a tree T is

Diameter(T) = max( Diameter(T.left), Diameter(T.right), Height(T.left)+Height(T.right)+1 )

 private class Data {  
   public int height;  
   public int diameter;  
 }  

 private void diameter(TreeNode root, Data d) {  
   if (root == null) {  
     d.height = 0; d.diameter = 0; return;  
   }  
   diameter(root.left, d); // get data in left subtree  
   int hLeft = d.height;  
   int dLeft = d.diameter;  
   diameter(root.right, d); // overwrite with data in right tree  
   d.diameter = Math.max(Math.max(dLeft, d.diameter), hLeft+d.height+1);  
   d.height = Math.max(hLeft, d.height) + 1;  
 }  

 public int diameter(TreeNode root) {  
   Data data = new Data();  
   diameter(root, data);  
   return data.diameter;  
 }

ChrisBangle · Accepted Answer · 2015-05-13 17:16:00Z

1

public class NodeWrap{
    int height = 0;
    int maxLength = 0;
    public NodeWrap(int h, int m){
        height = s;
        maxLength = m;
    }
}


public NodeWrap getDiameter(BinaryNode root){
    if(root == null){
        return new NodeWrap(0, 0);
    }

    NodeWrap left = getDiameter(root.left);
    NodeWrap right = getDiameter(root.right);

    int height = Math.max(left.height + right.height) + 1;

    int maxLength = Math.max(left.maxLength, right.maxLength);
    if(left.height != 0 && right.height != 0){
        maxLength = Math.max(left.height + right.height + 1, maxLength);
    }
    return new NodeWrap(singleLength, maxLength);
}

answered May 13, 2015 at 17:16

ChrisBangle

111 bronze badge

1 Comment

banarun Over a year ago

Can you answer the questions OP has posted? He did not ask for alternate code

Shashank Shandilya · Accepted Answer · 2019-07-09 08:53:59Z

1

One more O(n) solution in python,
code is self explanatory, only issue with this code is it returns tuple containing both height and diameter of the tree. 

def diameter(node, height):
  if node is None:
    return 0, 0
  leftheight  = 0
  rightheight = 0
  leftdiameter,  leftheight = diameter(node.left, leftheight)
  rightdiameter, rightheight = diameter(node.right, rightheight)
  rootheight = 1 + max(leftheight, rightheight ) 
  rootdiameter = ( leftheight + rightheight + 1 )
  return max( rootdiameter, leftdiameter, rightdiameter ), rootheight

answered Jul 9, 2019 at 8:53

Shashank Shandilya

394 bronze badges

Comments

arora · Accepted Answer · 2016-09-21 13:23:43Z

0

Neat and clean solution:

// way to use below util function:
prop p = new prop();
diameterUtil(root, p);
System.out.println(p.d);

class prop {
    int h;
    int d;
}

private void diameterUtil(Node n, prop p) {
    if (n == null) {
        p.h = 0;
        p.d = 0;
        return;
    }
    prop lp = new prop();
    prop rp = new prop();
    diameterUtil(n.left, lp);
    diameterUtil(n.right, rp);
    p.h = Math.max(lp.h, rp.h) + 1;
    p.d = Math.max((lp.h + rp.h + 1), Math.max(lp.d, rp.d));
}

answered Sep 21, 2016 at 13:23

arora

113 bronze badges

Comments

Yagami Light · Accepted Answer · 2017-07-09 09:04:37Z

Here is one recursive solution in C++ which gives you the height as well as diameter of binary tree.

struct tree
{
    int height = -1;
    int diameter = 0;
};

struct tree BSTDiameter(struct node *root)
{
    struct tree currentTree, leftTree, rightTree;
    if (root == NULL)
    {
        currentTree.height = -1;
        currentTree.diameter = 0;
        return currentTree;
    }
    leftTree = BSTDiameter(root->left);
    rightTree = BSTDiameter(root->right);
    currentTree.height = ((leftTree.height > rightTree.height) ? leftTree.height : rightTree.height) + 1;
    if (leftTree.height == -1 || rightTree.height == -1)
        currentTree.diameter = 0;
    else
        currentTree.diameter = (leftTree.height + rightTree.height + 3) > (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter) ? (leftTree.height + rightTree.height + 3) : (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter);
    return currentTree;
}

The time complexity of this is O(h) where h is height of the tree. Hope that helped you.

vijay9908 · Accepted Answer · 2020-04-11 08:53:30Z

The most efficient way is to compute diameter along with height to get to O(n) and here is the easiest way to get so [Python3,PyPy3]

for this definition for a binary tree node,
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
    self.height = 1

    def height(node):
        if node is None:
            return 0
        l_height = height(node.left)
        r_height = height(node.right)
        self.height = max(self.height,l_height+r_height+1)
        return max(l_height,r_height) + 1

    height(root)
    return self.height-1

The most simplest and affordable solution with faster runtime and lower complexity.

Collectives™ on Stack Overflow

Diameter of Binary Tree - Better Design

11 Answers 11

5 Comments

1 Comment

4 Comments

3 Comments

2 Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

11 Answers 11

5 Comments

1 Comment

4 Comments

3 Comments

2 Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related