Friday, December 23, 2011

Find Diameter of Binary Tree

So this question asks us to find Number of Nodes on the Longest Path in Binary Tree so one thing is sure that this path comprises on two leaves with maximum distance in BT..isn't it
PS:Don't confused with finding the maximum distance between two nodes in Binary Tree(as it doesn't involves 2 leaves)
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with same 7 as a diameter but different orientation. (also note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
Binary_tree_diameter1binary_tree_diameter2
Diameter 7 in both cases
The diameter of a tree T is the largest of the following quantities:
  • the diameter of T’s left subtree
  • the diameter of T’s right subtree
  • the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
Java code to get the diameter of the Tree
/* function to create a new node of tree and returns pointer */
Node newNode(int data);

/* returns max of two integers */
int max(int a, int b);

/* The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
    height and right heights */
return 1 + max(height(node->left), height(node->right));
}

/* Function to get diameter of a binary tree */
int diameter(Node tree)
{
/* base case where tree is empty */
if (tree == null)
return 0;

/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);

/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

/* Return max of following three
  1) Diameter of left subtree
  2) Diameter of right subtree
  3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}


Time Complexity O(n)
Space Complexity O(1)

1 comment:

  1. the complexity is O(n^2) . since each node is visit multiple times as the traversal is top bottom and not bottom up.

    ReplyDelete