Amazon Interview Question
Software Engineer InternsCountry: United States
int d(Node node) {
if (node == null) {
return 0;
}
return 1 + Math.max(d(node.left), d(node.right));
}
straightforward O(n) solution:
do InOrder Traversal, and maintain two variables (a max and a counter) as follows: while traversing in depth increment counter (and while walking up decrement it), when you hit a leaf node do a check to see if a counter value is greater than the max value. If so - update max variable, then continue traversing.
#include <iostream>
using namespace std;
class tree {
public:
tree *left;
tree *right;
int data;
tree(tree *l,tree *r, int d) : left(l), right(r), data(d) { }
};
int findMaxDepth(tree *node)
{
if (node == 0) {
return 0;
}
return (max(findMaxDepth(node->left), findMaxDepth(node->right))) + 1;
}
int main() {
// your code goes here
tree *root, *buffy, *dummy;
root = buffy = new tree(0,0,1);
for (int i = 2; i < 100; i++) {
dummy = new tree(0,0,i);
if (rand() % 2) {
buffy->left = dummy;
buffy = buffy->left;
} else {
buffy->right = dummy;
buffy = buffy->right;
}
}
cout << "depth " << findMaxDepth(root);
return 0;
}
- techinterviewquestion.com January 31, 2016