CareerCup

A node might not be an ancestor to its nearest leaf node.

1
                /              \
               2               3
           /          \
          4            5
        /     \          /     \
       6      7       8        9
     /  \       /  \     /   \     /  \
    10 11 12 13 14 15 16 17

In the above case, the nearest leaf node to 2 is 3.

We want to traverse the tree using DFS, storing the minimum height and the closest descendant leaf at each node:

1(1, 3)
                /               \
            2(3, 10)      3(0, 3)
           /       \
        ...        ...

Then starting from the given node, we want to go up to the root and check the path which is the shortest.

So in this case, nearest leaf to 2 is at distance
min(3, 1+1) = 2

Suppose the tree looked something like:

N(hN, cN)
             /                             \
      NL(hNL, cNL)                 NR(hNR, cNR)
    /                      \                          /                   \
 NLL(hNLL,..)   NLR(hNLR,..)   NRL(hNRL,..) NRR(hNRR, cNRR)
 /                 \     /                 \     /                \    /                      \
 ...     ... ...       .. ...           ...      ...

Then the leaf closest to NLRLLR would be the corresponding leaf node to
min(hNLRLLR, 1+hNLRLL, 2+hNLRL, 3+hNLR, 4+hNL, 5+hN)

O(N) time, O(N) extra space

The question should be asking for 'a' nearest leaf node, because there can be many leaf nodes 'nearest' to the given node. For ex: full binary trees, say of sizes, 1, 3, 7, 15 etc have all the leaf nodes at the same height from the root and all are the nearest.

As far as the solution is concerned, doing a level order traversal from the given node and printing out the first leaf encountered should solve the problem.

May be Dijkstra's algorithm will help.

I have simple approach for the above problem...which are as
1. Find the height of the tree...(considering leaf node can be on any height for more than one node)
2.Now Traverse at each level from i=0 to each height of the tree...

if i==height &&Root->left==NULL&&Root->right==NULL

you are done

My code goes like this... in c++

typedef struct Tree_Structure
{
    int data;
    struct Tree_Structure *left;
    struct Tree_Structure *right;
}Tree;
 
int HeightOfTree(Tree *Root)
{
    int n=0,m=0;
    if(!Root)return 0;
    n=HeightOfTree(Root->left);
    m=HeightOfTree(Root->right);
    if(n>m)
    return n+1;
    else 
    return m+1;
}
Tree *Level(Tree *Root,int i,int height)
{  Tree *temp=NULL;
    if(!Root)return NULL;
    if(i==height&&(Root->left==NULL&&Root->right==NULL))
    return Root;
    temp=Level(Root->left,i+1,height);
    if(temp)
    return temp;
    temp=Level(Root->right,i+1,height);
    if(temp)
    return temp;
}
Tree *NearestLeafNode(Tree *Root)
{   Tree *temp=NULL;
    if(!Root)
     return NULL;
     int height=HeightOfTree(Root);
     for(int i=0;i<height;i++)
      {
          temp=Level(Root,0,i);
          if(temp)
          return temp;
      }
}

A more simple code than above .... doing preorder traversal and keeping the lowest leaf position

void NLN(Tree *Root,Tree **temp,int level)
{
    static int s=1000;
    if(!Root)
     return ;
     if(Root->left==NULL&&Root->right==NULL&&s>=level)
     {
         *temp=Root;
         s=level;
         return;
     }
     NLN(Root->left,temp,level+1);
     NLN(Root->right,temp,level+1);
}
//Icalling like this
Tree *temp;
 NLN(Root,&temp,0);
   if(temp)
   cout<<endl<<temp->data;

First, do In-order traversal and for each leaf node, maintain its height and get height of node-of-interest as well. You need to do it for all leaf nodes because you don't know where your node-of-interest lies. - O(N)
Now, find minimum difference between height of node-of-interest and height of leaf node and print the leaf with min difference - O(N)

The term "nearest" is quite vague. It is unclear whether it means level-wise, or predecessor/ancestor of a given node in sorted order of the values of the nodes. Following code addresses the nearest when it is interpreted as successor node of a given node. It is an O(n) algorithm:

void NearestSuccessor(struct bst *b, int node, struct bst **nearest)
{
	if(b)
	{
		if(b->data>node && *nearest==NULL)
			*nearest=b;
		else if(b->data>node && *nearest!=NULL)
			if(b->data<(*nearest)->data)
				*nearest=b;
		NearestSuccessor(b->lc,node,nearest);
		NearestSuccessor(b->rc,node,nearest);
	}
}

It can be simply turned into "predecessor" case by swapping the greater than with less than checks.
However, if "nearest" is considered as nearest at the same level, then we essentially search for the right node of a node in a given level. It is apparent that all right nodes would have NULL nearest in such a case. The following is to address the level-order nearest. It is an O(lg n) algorithm.

struct bst* LevelOrderNearest(struct bst *b)
{
	int level1=0;
	int level2=0;
	if(b==NULL || b->parent==NULL)
		return NULL;
	if(b->parent->rc!=NULL && b->parent->rc!=b)
		return b->parent->rc;
	struct bst *tmp=NULL;
	struct bst *tmp1=b;
	while(b->parent!=NULL)
	{
		tmp=b;
		b=b->parent; 
		level1++;
		if(b->rc!=NULL && b->rc!=tmp)
			break;
	}
	while(level2!=level1-1)
	{
		if(b->rc==NULL)
			return NULL;
		b=b->rc;
		level2++;

	}
	if(b->rc==tmp1)
		return NULL;
	if(b->lc!=NULL)
		return b->lc;
	else if(b->rc!=NULL)
		return b->rc;
	else
		return NULL;
}

If we have the pointer to required node, why not use BFS to traverse down from that node? BFS finds the shortest path length-wise between 2 nodes in a graph, so it is guaranteed to find the closest leaf.

what about BFS?

As mentioned before a closest leaf can be above the current node, so BFS will wprk only if you have the parent ponter for every node (and not only left and right).

If so we can:
1. Find the specific node to start from (using a simple traversal algorithm).
2. Use BFS to calculate the shortest path to every leaf while treating the tree as a graph (it has left, right and parent).
3. To optimize the solution we will keep track of the shortest path untill now and once a traversal is longer than that there is no need to continue down/up that path.

Step 1 takes O(nlogn)
Step 2 will take an aditional (worst case) O(nlogn)
so total of O(nlogn) - however notice that step 3 will make sure that we do not actually travese the entire tree.

three cases we need to take care of
1.) if the node in question is root
2.) if node is not the rott
3.) node itself is the leaf

because we have second case we need to keep a track of the paths from root to all the leafs and then provide the solution base on these 2 sub cases
if the path were node is identified is the shortest pat or the lowest root path to leaf + rootpath to node is the shortest path.

proposed alogrithm is
O(N) to traverse all the leafs and O(N) space to keep the track of node paths for each DFS from root

Let's call our node v.

1. First, make a copy of the tree, let's call it T'
2. Next, reroot T' in v - it takes O(n) time
3. Run BFS from v. First discovered leaf it's the closest leaf to the v

All take O(n) time and O(n) additional space.

node *nearest(node *p){

if(p==NULL)
return;

if(p->left)
node *lc=nearest(p->left);
if(p->right)
node *rc=nearest(p->right);

if level(lc)<level(rc)
return lc;
}


// label levels of nodes using breadth first traversal

We can traverse the given tree in O(n) to store all the leaf nodes in a table. Then, we ca use these values to find the closest leaf node to a given node. Its worst case scenario is O(n).

void FindLeafNodes(struct BinaryTree *b, int *LeafNodes, int &index) //index=0 initially
{
	if(b)
	{
		if(b->lc == NULL && b->rc == NULL)
			LeafNodes[index++]=b->data;
		FindLeafNodes(b->lc,LeafNodes,index);
		FindLeafNodes(b->rc,LeafNodes,index);
	}
}

int FindClosestLeafNode(struct BinaryTree *node, int *LeafNodes, int index)
{
	try
	{
		if(node==NULL || LeafNodes==NULL || index<=0) throw "\nInvalid Input\n";
	}catch(const char *s)
	{
		puts(s);
		return INT_MIN;
	}
	int ClosestLeaf=INT_MIN;
	for(int i=0;i<index;i++)
	{
		if(b->data<LeafNodes[i] && LeafNodes[i]<ClosestLeaf)
			ClosestLeaf=LeafNodes[i];
	}
	delete [] LeafNodes;
	return ClosestLeaf;
}

Start a BFS from the given node as source node. The first leaf node we encounter will be the nearest leaf.

Node* findNearestNode(Node* givenNode)
{
	//We will assume that getParent() functions exist.
	//Amazon interviewer allowed it in my case, so its reasonable....
	
	Node* parent = givenNode()->getParent();
	Queue<Node> queue;
	
	//Make given Node as root and parent as right node.
	switchParentChildRelationship(parent, givenNode);
	
	queue.push(givenNode->getRight());
	queue.push(givenNode->getLeft());
	
	while(queue->peek() != null) 
    { 
		Node* node = queue.pop();
		if(node->getRight() == null && node-->getLeft() == null)
		   return node;
		else
		{
			if(node->getRight() == null)
			    queue.push(node->getLeft());
		    else if(node->getLeft() == null)
			    queue.push(node->getRight());
			else
			{
				queue.push(node->getRight());
				queue.push(node->getLeft());
			}
		}
		 
		
    }	
}

void switchParentChildRelationShip(Node* parent, Node* child)
{
	if(parent->getLeft() == child)
	{
		Node* childRight = child->getRight();
		child->setRight(parent);
		parent->setLeft(childRight);
	}
	if(parent->getRight() == child)
	{
		Node* childLeft = child->getLeft();
		child->setLeft(parent);
		parent->setRight(childLeft);
	}
}

A recursive procedure is possible.

A leaf closest to a node is that leaf which is closest to its left child and closer than closest leaf of its right child; or is closest to its right child and closer than closest leaf of its left child.

Assume we have a procedure which returns closest child of a root

int find_closest_leaf(node *root, node **closest_leaf)
{
	node	**left_closest_leaf,**right_closest_leaf;
	if( root == 0 )
	{
		closest_leaf = 0;
		return 0;	
	}
	int left = find_closest_leaf( root->left, left_closest_leaf) 
	int right = find_closest_right( root->right, right_closest_leaf)
 	if( left <= right ) 
		closest_leaf = left_closest_leaf; 
	else	
		closest_leaf = right_closest_leaf; 
}

More improvement is possible, however idea is to find leaf closest to left child, leaf closest to right child and chose one of the leaves which is closer;