Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
int distance_to_leaf(Node* root) {
vector<pair<Node*, int> > stack;
stack.push_back(make_pair(root, -1));
int maxDist = -1;
while (stack.size() > 0) {
pair<Node*, int> curr = stack.back();
Node* n = curr.first;
stack.erase(stack.end()-1);
if (!n->left && !n->right)
maxDist = max(maxDist, curr.second);
if (n->left)
stack.push_back(make_pair(curr.first->left, curr.second+1));
if (n->right)
stack.push_back(make_pair(curr.first->right, curr.second+1));
}
return maxDist;
}
//Modifying ti get what is required by interviewer
int FindDiffBwMinMaxdisttoleaf(Node* root, int *diff) {
vector<pair<Node*, int> > stack;
stack.push_back(make_pair(root, -1));
int maxDist = -1;
int minDist = (1<<31)-1;
int *diff = 0;
while (stack.size() > 0) {
pair<Node*, int> curr = stack.back();
Node* n = curr.first;
stack.erase(stack.end()-1);
if (!n->left && !n->right){
maxDist = max(maxDist, curr.second);
minDist = min(minDist, curr.second);
}
if (n->left)
stack.push_back(make_pair(curr.first->left, curr.second+1));
if (n->right)
stack.push_back(make_pair(curr.first->right, curr.second+1));
}
*diff = maxDist-minDist;
return diff;
}
the stack (which is actually a vector) Martin uses is not the same as the "stack" mentioned by the interviewer, the interviewer meant the call stack caused by recursion......
though I think using a queue instead of vector, same idea, but seems simpler for understanding....: what do you guys think ? :)
int difference(Node* root)
{
if(!root)
return 0;
int closest = 0;
int furthest = 0;
queue<pair<Node*, int>> nodes;
nodes.push(pair<Node*, int>(root,0));
while(!nodes.empty()) {
pair<Node*, int> n=nodes.front();
nodes.pop();
if(!n.first->left&&!n.first->right) {
if(closest == 0) {
closest = n.second;
} else {
furthest = n.second;
}
} else {
if(n.first->left) {
nodes.push(pair<Node*,int>(n.first->left,n.second+1));
}
if(n.first->right) {
nodes.push(pair<Node*,int>(n.first->right,n.second+1));
}
}
}
return (furthest>closest)?(furthest-closest):0;
}
Here is my solution in C# using two lists, one is for the current level being examined and the other one is for the next level. Length of the lists are not dependent on the depth of the tree. Actually it traverses the tree level by level like BFS.
public static int GetDifference(TNode node)
{
int minHeight = Int32.MaxValue;
int level = 0;
List<TNode> list = new List<TNode>();
list.Add(node);
List<TNode> next = new List<TNode>();
while (list.Any())
{
level++;
next.Clear();
foreach (TNode n in list)
{
if (n.left != null)
next.Add(n.left);
if (n.right != null)
next.Add(n.right);
if (n.left == null && n.right == null)
{
if (minHeight > level)
minHeight = level;
}
}
list.Clear();
list.AddRange(next);
}
return level - minHeight;
}
Use a special node called marker node. First, push the root and the marker node into the queue. Then, Every time you encounter that node, increase the height and push the marker node back into the queue. (to avoid getting into a loop, you also have to check whether the queue is empty whenever you dequeue a marker node.)
DFS Iterative version:
private static int heightDiffFromClosestToFarthestLeafFromRoot(TreeNode01 root) {
if(root.left == null || root.right == null) {
System.out.println("There are no 2 leafs from the root");
return 0;
}
Stack<TreeNode01> s = new Stack<TreeNode01>();
TreeNode01 curr = root;
int maxHeight = -1, minHeight = Integer.MAX_VALUE;
int lh = 0, rh = 0;
boolean done = false; boolean lchild = false;
while (!done) {
if (curr != null) {
s.push(curr);
curr = curr.left;
if(curr != null) {
lchild = true;
lh++;
}
} else {
if (!s.empty()) {
curr = s.pop();
if(curr.left == null && curr.right == null) {
if(lh < minHeight && lh > 0) {
minHeight = lh;
if(rh < minHeight && rh > 0) {
minHeight = rh;
}
}
if(lh > maxHeight && lh > 0) {
maxHeight = lh;
if(rh > maxHeight && rh > 0) {
maxHeight = rh;
}
}
}
if(lchild) {
lh--;
lchild = false;
}
curr = curr.right;
if(curr != null) {
rh++;
}
}
else {
done = true;
}
}
}
return maxHeight - minHeight;
}
The above code has some problems. This is the corrected one:
private static int heightDiffFromClosestToFarthestLeafFromRoot(TreeNode01 root) {
Stack<TreeNode01> s = new Stack<TreeNode01>();
TreeNode01 curr = root;
int maxHeight = -1, minHeight = Integer.MAX_VALUE;
int height = 0;
boolean done = false;
boolean lchild = false;
while (!done) {
if (curr != null) {
s.push(curr);
curr = curr.left;
if (curr != null) {
lchild = true;
height++;
}
} else {
if (!s.empty()) {
curr = s.pop();
if (curr.left == null && curr.right == null) {
if (height > maxHeight) {
maxHeight = height;
}
if (height < minHeight) {
minHeight = height;
}
}
if (curr.right != null) {
lchild = false;
}
if (lchild) {
height--;
}
curr = curr.right;
if (curr != null) {
height++;
lchild = false;
}
} else {
done = true;
}
}
}
return maxHeight - minHeight;
}
class TreeNode {
TreeNode left;
TreeNode right;
}
class MyData {
TreeNode node;
int depth;
public MyData(TreeNode n, int d) {
node = n;
depth = d;
}
}
TreeNode root = …;
Queue<MyData> q = new Queue();
q.append(new MyData(root, 0));
int min = Integer.MAX_VALUE;
int max = 0;
while (MyData data = q.pop() != null) {
if (data.left == null && data.right == null) {
if (data.depth < min) {
min = data.depth;
}
if (data.depth > max) {
max = data.depth;
}
continue;
}
if (data.left != null) {
q.append(new MyData(data.left, data.depth + 1));
}
if (data.right != null) {
q.append(new MyData(data.right, data.depth + 1));
}
}
return max - min;
#include <iostream>
#include <cmath>
using namespace std;
//return number of digits
int num_digits(int n){
int digit = 0;
while(n>0){
digit++;
n = n/10;
}
return digit;
}
//return first-second
int mcompare(int first, int second){
int diff;
int nf = num_digits(first);
int ns = num_digits(second);
diff = (first*pow(10,ns)+second) - (second*pow(10,nf)+first);
return diff;
}
void merge(int arr[], int begin, int mid, int end){
int begin1=begin, end1=mid, begin2=mid+1, end2=end;
int tarr[end-begin+1];
int i=0;
while(begin1<=end1 && begin2<=end2){
if(mcompare(arr[begin1], arr[begin2])<0){
tarr[i++] = arr[begin2++];
}else{
tarr[i++] = arr[begin1++];
}
}
if(begin1>end1){
while(begin2<=end2){
tarr[i++] = arr[begin2++];
}
}else{
while(begin1<=end1){
tarr[i++] = arr[begin1++];
}
}
i--;
while(i>=0){
arr[begin+i] = tarr[i];
i--;
}
}
void msort(int arr[], int begin, int end){
if(begin == end){
return;
}
if(begin+1 == end){
if(mcompare(arr[begin], arr[end])<0){
int tmp = arr[begin];
arr[begin] = arr[end];
arr[end] = tmp;
}
return;
}
int mid = (end-begin)/2 + begin;
msort(arr, begin, mid);
msort(arr, mid+1, end);
merge(arr, begin, mid, end);
}
int main(int argc, char **argv){
int arr[] = {9, 4, 94, 4, 14, 1};
int n = sizeof(arr)/sizeof(int);
//cout<<"\nn: "<<n;
cout<<"\nInitial array: ";
for(int i=0; i<n; i++){
cout<<arr[i]<<" ,";
}
msort(arr, 0, n-1);
cout<<"\nSorted array: ";
for(int i=0; i<n; i++){
cout<<arr[i]<<" ,";
}
return 1;
}
int solve(TreeNode* root)
{
queue< pair<TreeNode*, int> > q;
if (root != NULL) return q.push( make_pair(root, 1) );
int ans(-1), closest(0) ;
while (!q.empty())
{
TreeNode* cNode = q.top().first;
int cLevel = q.top().second;
if (is_leaf(cNode)) {
if (!closest) { closest = cLevel; }
else { ans = cLevel - closest; }
}
else {
if (cNode->left) q.push( make_pair(cNode->left, cLevel+1) );
if (cNode->right) q.push( make_pair(cNode->right, cLevel+1) );
}
}
return ans;
}
int DiffHeight(Tree *root, int min,int max, int height)
{
if(root == NULL)
return;
if(root->left == NULL && root->right == NULL)
{
if(height < min)
min = height;
if(height > max)
max = height;
}
else
{
DiffHeight(root->left, min, max, height+1);
DiffHeight(root->right, min, max, height+1);
}
}
The question mentioned a request to avoid using stack since the tree is too long. So this is an n^2 solution using O(1) memory:
public static int findLeavesDiff(ColorableNode tree) {
int minLeaf = Integer.MAX_VALUE;
int maxLeaf = Integer.MIN_VALUE;
while(tree.hasDiscoloredLeft() || tree.hasDiscoloredRight()){
ColorableNode node = tree;
int level = 0;
while(true){
if(node.hasDiscoloredLeft()){
level++;
node = node.left;
}else if(node.hasDiscoloredRight()){
level++;
node = node.right;
}else{
node.color = 1;
if(node.isLeaf()){
minLeaf = Math.min(level, minLeaf);
maxLeaf = Math.max(level, maxLeaf);
}
break;
}
}
}
return (maxLeaf == Integer.MAX_VALUE) ? 0 : maxLeaf - minLeaf;
}
Use BFS to find the closest leaf node first and then when the bfs exits, you have the leaf at the farthest level. Find the difference.
- Primus October 13, 2012