|
Write a C code to find Leftmost right cousin at the same leve .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
48. Write a C code to find Leftmost right cousin at the same leve .....
Question:
Write a C code to find Leftmost right cousin at the same level.
For ex:
10
/\
2 3
/\ /\
8 56 9
Leftmost right cousin of 5 is 6. Leftmost right cousin of 3 is NULL.
maybe an answer:
#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
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;
}
};
maybe an answer2:
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
maybe an answer3:
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{head});
}
private static Node TraverseTree(Node target, List 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);
}
}
(Continued on next question...)
Other Interview Questions
| 