Amazon Interview Question
Software Engineer / DevelopersWe can have recursive function
int length(Node *root)
{
if(root == 0)
return 0;
int right= length(root->right);
int left= length(root->left);
if( left > right )
return 1+ left;
else
return 1+right;
}
Because maximum path length != maximum depth.
Consider a tree with root node 2, left child 1 and right child 3.
The longest path is 1-2-3, of length 3.
Maximum depth (with 2 as root) is 1.
The question did not state if it is a directed tree or undirected tree, but, since it is in the Trees&Graphs section and this is a well known problem :-), assume it is undirected.
maximum path != maximum depth assuming some root...
The question just says tree... it does not mention a root/directed edges etc.
I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.
Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.
Please let me know if you don't agree.
I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.
Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.
Please let me know if you don't agree.
I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.
Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.
Please let me know if you don't agree.
I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.
Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.
Please let me know if you don't agree.
I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.
Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.
Please let me know if you don't agree.
tree_height(mynode *p)
{
if(p==NULL)return(-1);
h1=tree_height(p->left)+1;
h2=tree_height(p->right)+1;
return(max(h1,h2));
}
TESTED and WORKING
How about using a wrapper function around the function tree_height(mynode*p) which calls it for all the nodes as root one by one. The maximum length for a tree would be the one which gives us maximum depth. Though this looks to be really inefficient if the number of nodes in the tree is large, but it is a correct solution.
How about using a wrapper function around the function tree_height(mynode*p) which calls it for all the nodes as root one by one. The maximum length for a tree would be the one which gives us maximum depth. Though this looks to be really inefficient if the number of nodes in the tree is large, but it is a correct solution.
Path is different than height.
A node's longest path = sum of left childs height, right childs height and 1. The maximum of this number is the longest path.
This assumes it’s a binary tree and also assumes that the root has a degree greater than 1. For example it could be a completely unbalanced binary tree with the right sub-tree of every node empty. So you only have left sub-trees and left links. In this case the longest path is from the only leaf, the last node, to the root.
Assuming Longest Path of the tree is the diameter of the tree, the distance from the the root to its leaf.
Start from an arbitrary node and run a Bread First Search. Note the last node visited. From this node, run a BFS again. The distance from this node to the last node visited is the diameter of the tree.
answer = dia of tree, my code[working] in CPP is posted below.
here "depth" and "dia" are passed as reference to collect the values, they are un-initialized.
void BST::getDiameter(Node *head, int& depth, int& dia)const throw() {
if (head == NULL) {
//to counter the addition of 1 for a leaf node
//depth is set to -1..........
depth = -1;
dia = 0;
return ;
}
int lDia;
int rDia;
int lDepth;
int rDepth;
getDiameter(head->left, lDepth, lDia);
getDiameter(head->right, rDepth, rDia);
depth = (lDepth > rDepth ? lDepth : rDepth) + 1;
// (A)
// / \
// (C) (B)
// \
// (D)
// totalDepth(A) = Depth(A->left) + Depth(A->right) +2 = 0+1 +2 = 3
// IND = Inter Node Distance
int IND = lDepth + rDepth + 2;
dia = (lDia > rDia ? (lDia>IND?lDia:IND) : (rDia>IND?rDia:IND) );
cout << "depth at " << head->data << " is:" << depth << " and dia is " << dia << endl;
}
int Diameter(node *start)
{
if(start == NULL) return -1;
int l = 1 + Diameter(start->left);
int r = 1 + Diameter(start->right);
if(maximum < l+r+1)
maximum = l+r+1;
cout << maximum<< endl;
return max(l,r);
}
the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.
int Diameter(node *start)
{
if(start == NULL) return -1;
int l = 1 + Diameter(start->left);
int r = 1 + Diameter(start->right);
if(maximum < l+r+1)
maximum = l+r+1;
cout << maximum<< endl;
return max(l,r);
}
the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.
int Diameter(node *start)
{
if(start == NULL) return -1;
int l = 1 + Diameter(start->left);
int r = 1 + Diameter(start->right);
if(maximum < l+r+1)
maximum = l+r+1;
cout << maximum<< endl;
return max(l,r);
}
the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.
int depth(node *start)
{
if(start == NULL) return 0;
if(start->left == NULL)
int l = depth(start->left);
else
int l = 1 + depth(start->left);
if (start->right == NULL)
int r = depth(start->right);
else
int r = 1 + depth(start->right);
if(diameter< l+r)
diameter = l+r;
cout << diameter<< endl;
return max(l,r);
}
int depth(node *start)
{
if(start == NULL) return 0;
if(start->left == NULL)
int l = depth(start->left);
else
int l = 1 + depth(start->left);
if (start->right == NULL)
int r = depth(start->right);
else
int r = 1 + depth(start->right);
if(diameter< l+r)
diameter = l+r;
cout << diameter<< endl;
return max(l,r);
}
void findDiameter( node root,int& diameter,int& depth)
{
if (root->NULL)
{
depth = 0;
diameter = 0;
return 0;
}
findDiameter( root->left,diameterleft,depthleft);
findDiameter( root->right,diameterright,depthright);
diameter = max( depthleft+depthright+2, diameterleft,diameterright);
depth = max(depthleft+1,depthright+1);
}
void findDiameter( node root,int& diameter,int& depth)
{
if (root->NULL)
{
depth = 0;
diameter = 0;
return 0;
}
findDiameter( root->left,diameterleft,depthleft);
findDiameter( root->right,diameterright,depthright);
diameter = max( depthleft+depthright+2, diameterleft,diameterright);
depth = max(depthleft+1,depthright+1);
}
This looks pretty definitive to me:
h**p://crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/
I saw this link somewhere on careercup, can't find it now though. One thing the above doesn't do is, find the actual path; just the length. I suppose it would be easy to modify it though, to associate the node responsible, with each length, in a pair (or tuple, or custom struct) and return /that/ instead of just the length. I haven't actually tried it though.
find the height of each child node and go to the child with the largest height. return path when a null node has been reached.
int getHeight(Node *root){
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
else return max(getHeight(root->left), getHeight(root->right)) + 1;
}
int maxLevel(Node *root){
int h = getHeight(root);
int maxLevel = 0; int maxCount = 0;
for (int i = 1; i<=h; i++){
GNU nano 1.2.5 File: spiralOrder.cpp
int l = getHeight(root->left);
int r = getHeight(root->right);
if (l > r) return maxFuncUtil(root->left, path);
else return maxFuncUtil(root->right, path);
}
else {
return path;
/*
for (unsigned i = 0; i < path.size(); i++){
cout << path[i] << "\n";
*/
}
}
void maxPathFunc(Node *root){
vector <int> path;
vector <int> maxPath;
maxPath = maxFuncUtil(root, path);
for (unsigned i = 0; i < maxPath.size(); i++){
cout << maxPath[i] << " -> ";
}
cout << "\n" << "length: " << maxPath.size() << "\n";
}
If I remember correctly, one algorithm is to find the deepest node of the tree say D1, then assuming that D1 is the root, find the deepest node again, say D2. D1 to D2 will be the longest path.
- T March 22, 2009If your tree has both child/parent pointers, this should be O(n) time algorithm, where n is the number of nodes. (assuming the tree is connected).