Clever Geek Handbook

Find the diameter of a binary tree

I am trying to find the diameter of a binary tree (the length of the path between any two nodes in a tree containing the maximum number of nodes.) In java.

my code snippet:

public int diametre(Node node, int d)
{
    if(node==null)
        return 0;

    lh=diametre(node.left, d);
    rh=diametre(node.right, d);

    if(lh+rh+1>d)
        d=lh+rh+1;

    return findMax(lh, rh)+1;
}

In the main method:

 System.out.println( bst.diametre(root,0) );

Logic: Its actually post-order logic. the variable 'd' refers to the diameter of the subtree (in this iteration). It will be updated as and when a larger value is found. 'lh' means: Left subtree height. "rh" means: the height of the right subset.

But this gives the wrong conclusion.

The tree is considered:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

Idle output: 5

But this code gives 3.

Can someone figure out where the problem is ...

+3


source to share


6 answers 


public int diameter (Node root)
{
    if (root == null) return 0;
    else return Math.max (
        diameter (root.left), 
        Math.max (
            diameter (root.right),
            height (root.left) + height (root.right) + 1));
}

public int height (Node root)
{
    if (root == null) return 0;
    else return 1 + Math.max (height (root.left), height (root.right));
}


+8


source


You will find the diameter of the tree by running a BFS from any node and then another BFS from a more distant node (the node was last visited during the first BFS). The diameter is formed by the node last visited in the first BFS and the node last visited in the first BFS. The fact that the tree is binary does not affect the algorithm.



EDIT: Changing the value d

in the code you write will not affect the argument you pass as primitive types are not passed by reference in java.

+1


source


I suggest the following:

public static TreeAttr calcTreeDiameter(Node root) {
    if (root == null)
        return new TreeAttr(0, 0);

    TreeAttr leftAttr = calcTreeDiameter(root.getLeft());
    TreeAttr rightAttr = calcTreeDiameter(root.getRight());

    int maxDepth = Math.max(leftAttr.depth, rightAttr.depth);
    int maxDiam = Math.max(leftAttr.diameter, rightAttr.diameter);
    maxDiam = Math.max(maxDiam, leftAttr.depth + rightAttr.depth + 1);

    return new TreeAttr(maxDiam, maxDepth + 1);
}

TreeAttr is a simple structure containing the diameter and depth of a subtree. Both must be passed in recursively, as the optimum can be either from one of the subtrees or from the concatenation of the longest paths.

+1


source 


int max=0;
public int diameter(Tree root) {
  if(root==null) return 0;
  int l=diameter(root.left);
  int r=diameter(root.right);
  max=Math.max(max,l+r+1);
  return l>r:l+1:r+1;
}

max is the maximum diameter.

0


source


Algo takes O (n). Calculates height and path at the same time.

public static int findLongestPath(TreeNode root)
{
  // longest path = max (h1 + h2 + 2, longestpath(left), longestpath(right);

  int[] treeInfo = longestPathHelper(root);

  return treeInfo[0];
}

private static int[] longestPathHelper(TreeNode root)
{
  int[] retVal = new int[2];

  if (root == null)
  {
     //height and longest path are 0
     retVal[0] = 0;
     retVal[1] = 0;
  }

  int[] leftInfo = longestPathHelper(root.getLeft());
  int[] rightInfo = longestPathHelper(root.getRight());

  retVal[0] = Math.max(leftInfo[1] + rightInfo[1] + 2, Math.max(leftInfo[0], rightInfo[0]));
  retVal[1] = Math.max(leftInfo[1], rightInfo[1]) + 1;

  return retVal;
}
0


source


You must use the height of the tree to calculate the diameter. Create a getHeight () function that takes the root of the tree as an argument and returns the height of the tree. Using this value and using recursion, we can calculate the diameter of the tree. Here is the code for it .....

Function for calculating the diameter: -

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

int rootDiameter = findHeight(root.getLeft()) + findHeight(root.getRight()) + 1;
int leftDiameter = getDiameter(root.getLeft());
int rightDiameter = getDiameter(root.getRight());

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

Function to calculate tree height: -

public static int findHeight(BinaryTreeNode node) {
if(node == null)
    return 0;

else {
    return 1+Math.max(findHeight(node.left), findHeight(node.right));
}
}
0


source






More articles:


All Articles