CareerCup

This is nothing but level order successor. We just have to write level order traversal code.

One more check is required whether successor is on same level or not.

I think it's a bit more complicated - how would your idea differentiate between cousins and siblings?

To be more clear, my understanding of the question is that f(8) = 6 (as 6 is a cousin), but your system would give f(8) = 5.

I guess a fairly simple additional check would be to ensure that the 2 nodes have different parents.

guysssss ..!!!!
how about this ...
use this 2 algo
find out the level of the node ..

then printf all the nodes at the given level ... put some condition or flag so that when current value becomes node value .. set the flag.. n just print the nxt value ...else return null . .

level order will do, just we can have some marker for each level in the queue

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

class BinaryTree
{

public:
BinaryTree* left;
BinaryTree* right;
int data;

BinaryTree(int value)
{
left = NULL;
right = NULL;
data = value;
}

static BinaryTree* BuildTree()
{
BinaryTree* root = new BinaryTree(10);
BinaryTree* n2 = new BinaryTree(2);
BinaryTree* n3 = new BinaryTree(3);
BinaryTree* n5 = new BinaryTree(5);
BinaryTree* n6 = new BinaryTree(6);
BinaryTree* n8 = new BinaryTree(8);
BinaryTree* n9 = new BinaryTree(9);

root->left = n2;
root->right = n3;
n2->left = n8;
n2->right = n5;
n3->left = n6;
n3->right = n9;

return FindLeftMostRightSibling(root, n8);
}

bool IsLeftChild(BinaryTree* someNode)
{
BinaryTree* leftSubTreePtr = this->left;
if(this == someNode)
{
return true;
}
if(leftSubTreePtr == NULL)
{
return false;
}

return leftSubTreePtr->left->IsLeftChild(someNode) || leftSubTreePtr->right->IsLeftChild(someNode);
}

static BinaryTree* FindLeftMostRightSibling(BinaryTree* root, BinaryTree* node)
{
std::vector<std::vector<BinaryTree*>> v;
std::vector<BinaryTree*> v0;
v0.push_back(root);
v.push_back(v0);

std::vector<BinaryTree*>::iterator it;
std::vector<BinaryTree*> myV = v0;
int depthOfNode = 0;
int depth = 0;
while(true)
{
std::vector<BinaryTree*> newVector;
for(it = myV.begin(); it != myV.end(); it++)
{
BinaryTree* nodePtr = *it;
if(node == nodePtr)
depthOfNode = depth;
if(nodePtr->left != NULL)
{
newVector.push_back(nodePtr->left);
}
if(nodePtr->right != NULL)
{
newVector.push_back(nodePtr->right);
}
}
if(newVector.size() > 0)
{
v.push_back(newVector);
myV = newVector;
depth++;
}
else
{
break;
}
}
std::vector<BinaryTree*> someV = v.at(depthOfNode);
for(it = someV.begin(); it != someV.end(); it++)
{
if(*it == node)
{
break;
}
}
if(it != someV.end())
{
it++;
for(; it!= someV.end(); it++)
{
if(root->IsLeftChild(*it))
continue;
return *it;
}
}
return NULL;
}
};

FL(n, k)
	if(n->d == d)
		return k
	prev = n
	FL(n->l, k+1)
	if(n == rt)
		bl = false
	FL(n->r, k+1)

ML(n, k)
	if(k == 0)
		return n->d
	ML(n->l, k-1)
	ML(n->r, k-1)
	
main
	k = 0
	n = rt
	bl = true
	FL(n, k)
	if(bl && k>0)
		return ML(rt->r, k-1)
	else if (k == 0)
		return Nil
	else
		return prev->r->d

<pre lang="" line="1" title="CodeMonkey91582" class="run-this"> class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
public object Value { get; set; }
}

class Program
{
public static Node GetLeftMostRightNode(Node head, Node target)
{
return TraverseTree(target, new List<Node>{head});
}



private static Node TraverseTree(Node target, List<Node> currentLayer)
{
List<Node> nextLayer = new List<Node>();
bool targetFound = false;
foreach (Node node in currentLayer)
{
if(node.Left != null)
{
if (targetFound)
{
return node.Left;
}
nextLayer.Add(node.Left);
}
if (node.Left == target)
{
targetFound = true;
}
if(node.Right != null)
{
if (targetFound)
{
return node.Right;
}

nextLayer.Add(node.Right);
}
if (node.Right == target)
{
targetFound = true;
}
}

if(targetFound || nextLayer.Count == 0)
{
return null;
}
else
{
return TraverseTree(target, nextLayer);
}
}



static void Main(string[] args)
{
Node A = new Node { Value = "A" };
Node B = new Node { Value = "B" };
Node C = new Node { Value = "C" };
Node D = new Node { Value = "D" };
Node E = new Node { Value = "E" };
Node F = new Node { Value = "F" };
A.Left = B;
A.Right = C;
B.Left = D;
B.Right = E;
C.Left = F;

Node result = GetLeftMostRightNode(A, E);

}
}</pre><pre title="CodeMonkey91582" input="yes">
</pre>

may be we can obtain the soln using node notaion

leftchild -> 2*parent+1;
rightchild -> 2*parent+2;

so to find the sibling
sibling -> ceil(childnode)*2+1;

correct me if i am wrong :)

Node* leftMostRightCousin(Node *node){
	if(!node) return 0;
	if(node->parent && node->parent->left == node){
		return node->parent->right;
	}
	int level = 0;
	Node *par = 0;
	while(true){
		par = node->parent;
		if(!par || !par->right) return 0;
		if(par->right == node){
			level++;
			node= par;
			continue;
		}
		level++;
		node = par;
		break;
	}
	if(!node->right) return 0;
	node = node->right;
	level--;
	while(level	> 0){
		if(node->left){
			node = node->left;
			level--;
			continue;
		}
		return node;
	}
	return node;

}

node *leftmost_rightsibling(node *tree,node *n)
 {
  node *sibling;   
  queue q=init_q();
  enqueue(q,tree);
  enqueue(q,NULL);
  while(!is_empty(q))
  {
    node *d=dequeue(q);
    if((d==NULL)&&(!is_empty(q)))
      enqueue(q,NULL);
   else if(d->value==n->value)
    {
       sibling=dequeue(q);
       if((sibling!=NULL)&&(d->parent==sibling->parent))
        return (dequeue(q))
       else
        return sibling;                      
    }    
    else
    {
      if(d->left)
        enqueue(q,d->left);
      if(d->right)
        enqueue(q,d->right);     
    }                  
  }    
  return NULL; 
}

Dear Mrs psychocoder,

There is one mistake in your code ;-
if((d==NULL)&&(!is_empty(q)))
enqueue(q,NULL);

We should be dequeueing it right ?


It looks like you're typing some code. Surround it with

and

to preserve whitespace properly.

node* leftmostcousin(node* root, int level,int value)
{
    if(root == NULL)
      return NULL;
      if(level<=0)
        return NULL;
        if(level ==1 &&(root->left->data == value ||root->right->data == value))
          return NULL;
          if(level ==1)
             {
                 if(root->left)
               return root->left;
               else if(root->right)
               return root->right;
               else 
                return NULL;
             }   
             node * lefti = leftmostcousin(root->left,level-1,value);
             if(lefti !=NULL)
              return lefti;
              else 
              return leftmostcousin(root->right,level-1,value);
              return NULL;
}