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, Aug 10 '12 at 07:23
arun, offcourse i have tested the code. I mean can there be a better algorithm? — Manish, Aug 10 '12 at 07:24
@Barth, thanks. Didnt know about code review. Will try there as well. — Manish, Aug 10 '12 at 07:33
@Manish Ohh ok. Please refer to this http://www.geeksforgeeks.org/archives/5687 — arunmoezhi, Aug 10 '12 at 07:33
Outside of an interview, is there any purpose for finding the diameter of a binary tree? — Jeff, Feb 15 '16 at 03:09

score 42 · Accepted Answer · edited Apr 30 '20 at 12:03

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 '20 at 12:03

Vrashabh Irde

14,129
6
51
103

answered Aug 10 '12 at 07:49

verdesmarald

11,646
2
44
60

1

@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. – AKS Aug 16 '13 at 17:22
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. – JavaDeveloper Sep 19 '13 at 19:35
2

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. – kirakun May 30 '14 at 03:49
@kirakun, Should not the diameter be 0 (or length to root * 2) in this case? – unknown_boundaries Mar 11 '15 at 06:12
2

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());` – Ermias K Apr 11 '20 at 18:49

score 41 · Answer 2 · edited Oct 26 '14 at 12:26

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.

The line `int[] rightResult = getDiameter(root.getLeft());` should probably be: `int[] rightResult = getDiameter(root.getRight());`? — Patrizio Rullo, Aug 11 '14 at 11:31

nem035 · Answer 3 · 2016-01-16T10:20:14.147

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 '16 at 10:20

answered Aug 27 '14 at 00:42

nem035

34,790
6
87
99

+1 .. Thanks for the solution. Why should we keep them in a wrapper class? I have seen the [link](http://www.geeksforgeeks.org/diameter-of-a-binary-tree/) 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? – Amarnath Sep 12 '15 at 15:03
2

Hi @Che, the reason you need a wrapper class is because Java is [Pass By Value](http://javadude.com/articles/passbyvalue.htm) 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](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) – nem035 Sep 12 '15 at 18:39
@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. – Aditya Joshee Jul 30 '16 at 15:33
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. – nem035 Jul 30 '16 at 17:41

score 4 · Answer 4 · edited Aug 10 '12 at 09:22

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 '12 at 09:22

stakx - no longer contributing

83,039
20
168
268

answered Aug 10 '12 at 07:39

Xavier Delamotte

3,519
19
30

2

This doesn't give you the diameter, it gives you the depth. – Keppil Aug 10 '12 at 07:49
@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) – AKS Aug 16 '13 at 17:23
@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. – rliu Jan 20 '14 at 11:24

score 3 · Answer 5 · edited Aug 24 '17 at 10:41

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 '17 at 10:41

roottraveller

7,942
7
60
65

answered Mar 15 '15 at 02:58

shakirthow

1,356
14
15

Why are you using `diameter` as normal variable in method argument? – roottraveller Aug 24 '17 at 09:44
Can you please explain this algorithm ? I'm not able to get the concept of adding 1 in the return statement .. – Learner Dec 26 '19 at 07:56

score 2 · Answer 6 · answered Nov 10 '13 at 18:29

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

score 1 · Answer 7 · answered May 13 '15 at 17:16

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

Can you answer the questions OP has posted? He did not ask for alternate code — banarun, May 13 '15 at 17:30

score 1 · Answer 8 · answered Jul 09 '19 at 08:53

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

score 0 · Answer 9 · answered Sep 21 '16 at 13:23

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

score 0 · Answer 10 · edited Jul 09 '17 at 09:04

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.

score 0 · Answer 11 · answered Apr 11 '20 at 08:53

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.

Diameter of Binary Tree - Better Design

11 Answers11

Linked