CareerCup

doing bfs the last node which will be traversed is the rightmost node at maximum depth

Can you define with an example what right most node at maxDepth with a simple example?

test

here is the solution

Node* getRightmostAtDepth(Node* n, int depth, bool youAreLeft)
{
	static int currDepth = 0;

	if(depth == currDepth)
	{ 
		if( youAreLeft == false)
			return n;
		else return null;
	}

	if(n == null)
		return null;

	currDepth++;

	Node* R =  getRightmostAtDepth(n->right, depth, false);

	Node* L = getRightmostAtDepth(n->left, depth, true);

	if(R != null)
	{
		return R;
	}
	else if (L ! = null)
	{
		return L;
	}
	else
	{
		return null;
	}
}

main()
{
	...
	getRightmostAtDepth(head, 10, false);
}

O(n) time recursive

private Pair<Tree.Node, Integer> getDeepestAndRightMostNode(
    Tree.Node node, int ht) {
    if (node == null) {
        return null;
    }
    if (node.left == null && node.right == null) {
        return new Pair<Tree.Node, Integer>(node, ht);
    }
    Pair<Tree.Node, Integer> lResult =
        getDeepestAndRightMostNode(node.left, ht + 1);
    Pair<Tree.Node, Integer> rResult =
        getDeepestAndRightMostNode(node.left, ht + 1);
    if (lResult != null && rResult != null) {
        if (lResult.second > rResult.second) {
            return lResult;
        } else {
            return rResult;
        }
    }
    return (lResult == null) ? rResult : lResult;
}

// Assuming tree is not empty
public Tree.Node getDeepestAndRightMostNode(Tree tree) {
    return getDeepestAndRightMostNode(tree.root, 1).first;
}

class Node{
 Node left;
 Node right;
 int data;
};
class BarNode(
 Node max;
 int depth;
};
Node foo(Node root){
 if(root==null)
  return(null);
 BarNode maxNode = bar(root, 1);
 if(maxNode==null)
  return(null);
 else
  return(maxNode.max);
}
BarNode bar(Node root, int depth){
 if(root==null)
  return(null);
 if(root.left==null && root.right==null){
  BarNode bNode = new BarNode();
  bNode.depth = depth;
  bNode.max = root;
  return(bNode);
 }
 lBNode = bar(root.left, depth+1);
 rBNode = bar(root.right, depth+1);
 if(lBNode==null)
  return(rBNode);
 if(rBNode==null)
  return(rBNode);
 if(rBNode.depth>=lBNode.depth) // Prefers right node to left if they are at the same depth
  return(rBNode);
 return(lBNode); 
}

Someone has already suggested this, I am just clarifying:
Do a BFS and at each step insert the left node before right node in the queue. The last node in the queue would be the answer.
How to check if an element is last element in the queue? When you pop element from the queue, if the popped element has no children and queue is empty after popping it, you have found the last element.

BFS.. last node is the right most node with mxdepth

How's this one


class Tree{
Node root;
int rightMost=0;
int maxHeigth=0;
Node rightMostDeep;
public void findRightMostDepth(){
findRightMostDepthRecursive(root,0,0);
}

private void findRightMostDepthRecursive(Node temp,int x,int y){
if(temp!=null){
if(x>rightMost){
maxDepth = y;
rightMost = x;
rightMostdeep = temp;
}
findRightMostDepthRecursive(temp.left,x-1,y+1);
findRightMostDepthRecursive(temp.right,x+1,y+1);
}
}
}

void findRightMostHelper (Node* p, int& maxDepth, Node*& rNode, int depth){
  if (p == NULL) return;
  if (depth >= maxDepth){
    maxDepth = depth;
    rNode = p;
  }
  findRightMostHelper(p->left, maxDepth, rNode, depth+1);
  findRightMostHelper(p->right, maxDepth, rNode, depth+1);
}

int findRightMost (Node* p){
  int maxDepth = 0;
  Node* rNode = NULL;
  findRightMostHelper(p, maxDepth, rVal, 0);
}

I do not think that the problem is to find right most node.

If it is wrong then I guess the question would be
'Find a node right most node at depth D'
0
0 0
2 1 3 4
5 6
if the input is 3 then the answer would be 4 because the right most node at level 3 is 4.

now it is close to google interview question.

I think the problem is to find the rightmost node at given depth, as suggested there can be multiple solutions to this problem:
1. BFS O(n), average, worst case.
2. Traverse the tree check at any given level if node->right exists (offcourse when node.depth < D) , if yes recursively call routine to find if there exist a node at depth D. If not repeat the same for node.left.

Node *findNode(Node *root, int depth, const int D, Node **ret)
{
     if (*ret) {
          return; // terminate recursion
     }
     if (depth < 0) {
         return NULL; // invalid arguments.
     }
     if (depth == D) {
          *ret = root;
           return ;
     } else if (*depth > D) {
        assert (0, "we should never get here");
     }
     findNode(root->right, depth+1, D, ret);
     findNode(root->left, depth+1, D, ret);
 }