Google Interview Question
Country: United States
P.S. To avoid off-by-one errors, make sure you understand how you define height and diameter for segments. I define these lengths in terms of the number of nodes, so a segment from A to B to C has length 3 by my definition, not 2, despite 2 making more sense from a physical/intuitive perspective. Likewise, a tree with a single node has height 1 by definition.
If the Tree cannot be changed, I'll have to calculate hight for each node - it will take exponential time complexity.
would it make sanse to combine "hight" and "diameter" to be calculate at one traverse?
I think it works in linear time complexity to the number of nodes if we store them for quick access.
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> n = new HashMap<Integer, Integer>();
int maxDiameter(node root) {
if(root == null)
return 0;
if( n.containsKey(root.key))
return n.get(root.key);
int temp = max(maxDiameter(root.left), maxDiameter(root.right), findMaxDepth(root.left) + findMaxDepth(root.right) + 1);
n.put(root.key, temp);
return temp;
}
int findMaxDepth(node root) {
if(root == null)
return 0;
if(m.containsKey(root.key))
return m.get(root.key);
int temp = max(findMaxDepth(root.left), findMaxDepth(root.right)) + 1;
m.put(root.key, temp);
return temp;
}
}
#define max(a,b,c) ((a>b?a:b)>c?(a>b?a:b):c)
struct output {
int dia;
int height;
};
struct tree {
struct tree *left;
struct tree *right;
int data;
};
(struct output)getdiameter(struct tree *head) {
output o = malloc(sizeof(struct output));
output temp,temp1;
if (head == NULL) {
o.dia = 0;
o.height = 0;
return o;
}
if (head->left == NULL && head->right == NULL) {
o.dia = 0;
o.height = 1;
} else if (head->left == NULL || head->right == NULL) {
temp = malloc(sizeof(struct output));
temp = (head->right == NULL) ? getdiameter (head->left):getdiameter (head->right);
o.dia = max(temp.dia,temp.height+1, -1); // -1 just an attempt to reuse max finction
o.height = temp.height + 1;
} else {
temp = malloc(sizeof(struct output));
temp1 = malloc(sizeof(struct output));
temp = getdiameter (head->left);
temp1 = getdiameter (head->right);
o.dia = max(temp.dia,temp1.dia,temp.height + temp1.height + 1);
o.height = max(temp.height, temp1.height, -1) + 1; // -1 just an attempt to reuse max finction
}
return o;
}
do we really need height?
int diameterHelper(bst* head, int& y)
{
if(head==0)
return 0;
int left=diameterHelper(head->Left,y);
int right= diameterHelper(head->Right,y);
if(y < left+right+1)
y =(left+right)+1;
if(left>right)
return left+1;
else
return right+1;
}
int Diameter(bst* head)
{
int result=0;
diameterHelper(head,result);
return result;
}
#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
public:
node(int dat){ data = dat; left = NULL; right=NULL; }
int data;
node* left;
node* right;
};
/* returns max of two integers */
int max(int a, int b);
/* function to Compute height of a tree. */
int height(node* node);
/* Function to get diameter of a binary tree */
int diameter(node * tree)
{
/* base case where tree is empty */
if (tree == 0) 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 */
cout<< lheight + rheight + 1 <<" "<< ldiameter << " "<< rdiameter <<endl;
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */
/* 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));
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
/ \
6 7
*/
node *root = new node(1);
root->left = new node(2);
root->right = new node(3);
root->left->left = new node(4);
root->left->right = new node(5);
root->left->left->left = new node(6);
root->left->right->right = new node(7);
printf("Diameter of the given binary tree is %d\n", diameter(root));
cout<< "node 1 has height "<< height(root)<<endl;
return 0;
}
Just iterate through all the nodes
for each node find x = height of right subtree + height of left subtree + 2 if both subtrees r not null
if any1 of them is null x = height (right or left subtree ) + 1
else 0
and diameter = max(x) when u calculate x for each node
int height(mynode *ptr) //supporting height function {
int lheight=0,rheight=0;
if(ptr == NULL)
return 0;
lheight = height(ptr->left);
rheight = height(ptr->right);
if(lheight >= rheight)
return (lheight+1);
else
return (rheight+1);}
int max(int a, int b){ //supporting max function
if(a>b)
return a;
else
return b;}
int Diameter(mynode *root){
if(root == NULL)
return 0;
int lheight = height(root->left);
int rheight = height(root->right);
int ldiam = Diameter(root->left); //calculate left subtree diam
int rdiam = Diameter(root->right); //calculate right subtree diam
return max(lheight+rheight+1, max(ldiam,rdiam));
}
If the Tree cannot be changed, I'll have to calculate hight for each node - it will take exponential time complexity.
would it make sanse to combine "hight" and "diameter" to be calculate at one traverse?
Recursive single-pass Python solution:
def diameter_height(tree):
if tree is None: return (0,0)
left, val, right = tree
ld, lh = diameter_height(left)
rd, rh = diameter_height(right)
d = max([ld, rd, lh+rh+1])
h = max([lh+1, ld+1])
return d, h
def diameter(tree):
d, h = diameter_height(tree)
return d
assert 0 == diameter(None)
assert 1 == diameter((None, 1, None))
three_node_tree = ((None, 0, None), 1, (None, 2, None))
assert 3 == diameter(three_node_tree)
seven_node_tree = (three_node_tree, 'foo', three_node_tree)
assert 5 == diameter(seven_node_tree)
imbalanced_tree = (seven_node_tree, 'bar', None)
assert 5 == diameter(imbalanced_tree)
please don't use two recursion:
struct Node
{
Node* L;
Node* R;
int val;
};
int GetDiameter(Node* root,int& height)
{
if(!root)
{
height=0;
return 0;
}
int lHeight,rHeight;
int lDiameter=(root->L,lHeight);
int rDiameter=(root->R,rHeight);
int res=max(lDiameter,rDiameter);
res=max(res,lHeight+rHeight+1);
height=max(lHeight,rHeight)+1;
return res;
}
No recursion solution, use post-order traversal:
int GetDiameter2(int& height)
{
if(!root)return 0;
stack<Node*> s;
s.push(root);
Node* prev=NULL;
int res=0;
while(!s.empty())
{
Node* cur=s.top();
if(!prev || prev->L==cur || prev->R==cur)
{
if(cur->L)
s.push(cur->L);
else if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=1;
res=max(res,1);
}
}
else if(cur->L==prev)
{
if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=cur->L->tmp+1;
res=max(res,cur->L->tmp+1);
}
}
else if(cur->R==prev)
{
s.pop();
if(cur->L)
{
cur->tmp=max(cur->L->tmp,cur->R->tmp)+1;
res=max(res,cur->L->tmp+cur->R->tmp+1);
}
else
{
cur->tmp=cur->R->tmp+1;
res=max(res,cur->R->tmp+1);
}
}
prev=cur;
}
return res;
}
Does the code below sound right ?
int Dia(Node *n, int *h) {
if (n == NULL) {
*h = 0;
return 0;
}
int lh, rh;
int ld = Dia(n->left, &lh);
int rd = Dia(n->right, &rh);
//calculate height of this node
*h = max(lh,rh) + 1;
//return max of left subtree dia, right subtree dia or dia including this node
return max(max(ld,rd),lh+rh+1);
}
How about this one ?
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;
}
}
Write a function that returns a tuple/struct of two values for a given tree. The first value is the height, and the second value is the diameter length.
- showell30@yahoo.com February 22, 2013The terminating case is a an empty tree, which returns 0,0.
The recursive calculations are these:
height = max(height(left), height(left)) + 1
diameter = max(diameter(left), diameter(right), height(left)+height(right)+1)
To fully complete the exercise, have a helper function that calls the other function and returns only the diameter as the final answer.