CareerCup

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.

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;
}

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;
}

Iterative post oder traversal will do the trick here!

Use DFS algorithm to get the height of each path from the root to the leaf.

If using BFS and the tree is not full/complete how do you keep track of depth?

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;
}

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;
	}

Two operations wrapped up in one:

int FindHeightBetweenClosetLeafAndFarthestLeaf(Tree t)
{
return FindLongestPath(t, t.getRoot()) - FindShortestPath(t, t.getRoot());
}

Now just implement FindLongestPath and FindShortestPath