Friday, March 9, 2012

Microsoft Question: Find diameter of a binary tree

Problem: The diameter or width of a tree is the number of nodes on the longest path between two leaves in the tree.

Example:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Approach: Diameter of a binary tree = MAX(height of left sub-tree + height of right sub-tree,
diameter of left sub-tree,
diameter of right sub-tree)


Implementation:

    int diameter(Node* node, int& height)
    {
        int lh = 0, rh = 0, ld = 0, rd = 0;
        if(node == NULL)
        {
            height = 0;
            return 0;
        }

        ld = diameter(node->left, lh);
        rd = diameter(node->right, rh);

        height = max(lh, rh) + 1;

        return MAX(lh + rh + 1, ld, rd);
    }


Complexity: O(n)

4 comments:

  1. The height in the code should be replaced with *height

    ReplyDelete
  2. While I agree with your solution, I am having hard find figuring out why my solution might be incorrect. Appreciate your comments.

    As I see, we can maintain a max_sum variable and count the height of the left subtree (lh), height of right subtree (rh) and update the max_sum if lh + rh + 1 is its greater. We calculate this sum at each of the nodes in the tree.

    From your solution, ultimately the diameters will be calculated based on heights of the left and right subtrees at some point of time in the code.

    ReplyDelete