CareerCup

Carry out a Level Order Traversal and once you get the node that is given, the very next node would be the left most right cousin.

Just traverse till left most node,when you hit null,go to the root node of the current node and then go for its right child.

once you traverse down those are not cousin those are child so cousin should be in the same level but left most right cousin dint make any sense please help me to understand the question

is it leftmost right cousin in same level ?

Hi!

What about a BFS?

I would mark the empty nodes with some standard value. And than do a BFS : when I reach the level with the given data , I will check for the left most right position which should be the cousin .. and if it is a standard value of mine then return null else return the data from the node.
(Correct. I mean BFS)

I may not be sure, but the following part worked with one example at least. I didn't have time to testit with other examples. It is basically BFS.

Structure of the binary search tree used modified for BFS

typedef struct bsearch_tree
{
 int key;
 int level;
 struct bsearch_tree *parent;
 struct bsearch_tree *left;
 struct bsearch_tree *right;
}BSTREE;

The function

BSTREE* leftmost_right_cousin(BSTREE* T,int item)
{
 QUEUE Q;
 BSTREE *u,*this_parent;
 int find=0,find_level;
 if(T!=NULL)
 {
  init_queue(&Q);
  T->level = 0;
  enqueue(&Q,T);
  while(!is_empty(&Q))
  {
   u = dequeue(&Q);
   if(find) //we have found the node whose cousin we are trying to find
   {
    if(u->level==find_level && u->parent != this_parent) //the cousin will be in the same level of the tree but its parent will be different
     return u; //return the first node satisfying the condition
    else if(u->level > find_level) //we are looking at some node at a deeper level than the required node. So we must not have found any cousin (to the right of the given node and having a different parent)
     return NULL;
   }
   if(u->key == item) //found the node whose cousin we are looking for
   { find = 1; find_level = u->level; this_parent = u->parent;}
   if(u->left!=NULL)
   {
    u->left->level = u->level + 1; //basic BFS algo, Since left node is put first into Q and Q being FIFO we will be dequeuing nodes from left to right in a particular level
    u->left->parent = u;
    enqueue(&Q,u->left);
   }
   if(u->right!=NULL)
   {
    u->right->level = u->level + 1;
    u->right->parent = u;
    enqueue(&Q,u->right);
   }
  }
  return NULL; //we didn't find the node whose cousin we are looking for, so the given node doesn't exist in the first place
 }
 return NULL; //the tree has no nodes at all
}

As already stated in the comment, since we are using a Queue in BFS and we are enquing nodes from left to right in a particular level, I don't think we will require to mark the nodes Left or Right, doing which will actually require different implementations for the given node being Left/Right.

*The fn provided is subject to correction.

This is a question for Binary Search Tree.
So, we should make use of this fact.

Pseudocode::

**Do a binary Search to find the given node.
**Keep Track of a previous ancestor which has a right child and its level.
**If given node was a left child, its parent's right child will be its immediate right sibling,
**otherwise, its ancestor's right_child's leftmost node at the level of the given node will be its immediate right sibling.

Max Time: O(2*logn)
Space: O(1)

@ Sonesh,can we modify the node structure? Can we add one extra sibling pointer?

O(N) worst case. O(N) space.

1. BFS (left to right), using a queue and inserting empty node marker in the queue when a node is missing a child and a level marker when we hit a new level.

2. If we find the value, its cousin must be behind it in the queue and be before the next level marker. If it's an even node (counting from left) its first cousin is at least two nodes way. Otherwise its next node is at least one node away.

3. Pop off the queue until we find the next non empty cousin (return it) or we hit the level marker (return null).

This is somewhat complex and probably not optimal but it's the best I can come up with.

public Node getLeftmostRightCousin(int val) {
	if(root == null) {
		return null;
	}
	
	int curNodeFromLeft = 0;
	Queue<Node> nodeQueue = new LinkedList<Node>();
	Node levelMarker = new Node(-1);
	Node emptyNodeMarker = new Node(-1);
	boolean nextLevelEmpty = true;
	
	nodeQueue.add(root);
	nodeQueue.add(levelMarker);
	
	while(!nodeQueue.isEmpty()) {
		Node curr = nodeQueue.remove();
		
		if(curr == levelMarker) {
			if(nextLevelEmpty) {
				return null; // No more real nodes on the next level.
			}
			if(!nodeQueue.isEmpty()) {
				nodeQueue.add(levelMarker);
			}
			
			curNodeFromLeft = 0; // starting a new level
			nextLevelEmpty = true;
			continue;
		}
		
		// Find its nearest cousin!
		if(curr.value == val) {
			if(curNodeFromLeft % 2 == 0)  { // even node is left child. Next cousin is min two nodes to the right.
				nodeQueue.remove();
			}
			
			// Remove from the queue until we hit the first real node; that's our closest right cousin.
			while((nodeQueue.peek() == emptyNodeMarker) && (!nodeQueue.isEmpty())) {
				nodeQueue.remove();
			}
			
			if(!nodeQueue.isEmpty()) {
				if(nodeQueue.peek() != levelMarker) {
					return nodeQueue.remove();
				}
			}
			
			return null;
		}
		
		if(curr.left != null) {
			nodeQueue.add(curr.left);
			nextLevelEmpty = false;
		} else {
			nodeQueue.add(emptyNodeMarker);
		}
		
		if(curr.right != null) {
			nodeQueue.add(curr.right);
			nextLevelEmpty = false;
		} else {
			nodeQueue.add(emptyNodeMarker);
		}
		
		curNodeFromLeft++;
	}
	
	return null;
}

Here is my implementation using Java:

public static Node leftMostRight(Node root, Node target){
        if(root == null || isLeaf(root) || target == null)
            return null;
        Queue<Node> nodeQ = new ArrayDeque<Node>();
        boolean findTarget = false;
        nodeQ.offer(root);
        Queue<Integer> levelQ = new ArrayDeque<Integer>();
        levelQ.offer(1);
        int targetLevel=0;
        while(!nodeQ.isEmpty()){
            Node node = nodeQ.poll();
            int currentLevel = levelQ.poll();
            if(findTarget && target.parent != node.parent && currentLevel == targetLevel)
                return node;
            if(node.value == target.value){
                findTarget = true;
                targetLevel = currentLevel;
            }
            if(node.left != null){
                nodeQ.offer(node.left);
                levelQ.offer(currentLevel+1);
            }
            if(node.right != null){
                nodeQ.offer(node.right);
                levelQ.offer(currentLevel+1);
            }
        }
        return null;
    }

private static Node nextRight(Node root, int i) {
        Queue<Node> q1=new ArrayDeque();
        Queue<Node> q2=new ArrayDeque();
        q1.add(root);
        while(!q1.isEmpty()){

            Node value=q1.remove();
            if(value.data==i){
                return q1.remove();
            }
            else{
                if(value.left!=null) q2.add(value.left);
                if(value.right!=null) q2.add(value.right);
            }
            if(q1.isEmpty()){
                q1=q2;
                q2=new ArrayDeque<Node>();
            }

        }
        return null;

    }

1. Keep a pointer to grand parent of the node being searched.
2. After that easy to find the sibling of the parent and if they have any child nodes.

1. Find the node with the searched value for using the regular BST node lookup. Also look for the first time the branching happens for the left and start counting the nodes thereafter.
(If there is no branching, there can't be any next sibling)
2. If branching occurs again, keep a note of the node and reset count
3. The count is the distance b/w the LCA (at the location where branching occurred) of the sibling and the searched value.

4. Knowing the LCA node, start DFS until the depth traversed == count (from last step).

class Node(object):

    def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

def findcommonNode(node, val):

	isLeft = True

	nodeP = None
	count = 0

	while node != None:

		if node.data == val and isLeft:
			return nodeP, count
		if val < node.data :
			if node.right:
				nodeP = node
				count = 0
				isLeft = True
			node = node.left
		else:
			node = node.right
		count += 1

	return None, count

def nextSibling(node, i, count):

	if not node:
		return None
	if i == count:
		return node
	
	if node.left:
		node = nextSibling(node.left, i+1, count)
	elif node.right:
		node = nextSibling(node.right, i+1, count)

	return node

def findNextSibling(root, val):

	pNode, count = findcommonNode(root, 7)
	if pNode:
	sNode = nextSibling(pNode.right, 1, count)

	return sNode.data if sNode else None

1) Find the node, and keep track of level (say target node is found on level L)- time log N
2) Push each traversed node into a stack
3) When node is found
  a) Pop the stack to remove the parent of the target node
  b) If stack is empty then given node does not have a cousin; return
  c) Do DFS from the right child of the current top of the stack (which is the grand-parent of the target node) and return the first node at Level L

Time complexity is log N, space complexity log N

1. Do BFS right left.
2. Maintain a pointer to the previous element
3. Once the node is found, the previous element is the left most right child if and only if the key of the previous element is bigger than that of the node. If not there is no right sibling.

Space - O(log n)
time - O(n)

1. Find the root of the given "node" [ long n]. While doing so keep a track of the parent node.
2. Once found. Run a In-order traversal from the parent node found in step 1.
3. The first leaf node in the in-order traversal would be left-most right cousin.
time-complexity [ O(logN)

he said he already gave a BST, He obviously gives it in an array..!!Confirm from the interviewer that its accepted in In-order only

1.)Search for the Required node in the Array (which if found say is at i ),
2.)Nodes From (i+1---till---2i) are its Cousins

Hopefully im right!!!!

for this question, do we need a binary search tree, or just a binary tree?