Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Woud this work?
void connectRight(Node *t, Node *nextRight) {
if (!t)
return;
t->nextRight = nextRight;
connectRight(t->leftChild, t->rightChild);
if (nextRight)
connectRight(t->rightChild, nextRight->leftChild);
else
connectRight(t->rightChild, NULL);
}
void connect(Node *t) {
connectRight(t, NULL);
}
void PopulateNext(Node** root)
{
Node* tempNode = *root;
if (tempNode == NULL)
{
return;
}
if (tempNode->left)
{
tempNode->left->next = tempNode->right;
}
if (tempNode->right)
{
tempNode->right->next = temp->next->left;
}
PopulateNext(&tempNode->left);
PopulateNext(&tempNode->right);
}
Will this work?
For root node, after assign it to tempNode, there is no tempNode->next->left, thus we should put a null check inside tempNode->right branch and assign NULL to the rightpointer of rightmost element in each level
is the below condition right, because inorder successor of the left is the extreme left not of right child
if (tempNode->left)
{
tempNode->left->next = tempNode->right;
}
/*A binary tree is given with left and right populated but the nextRight pointers in each node are not populated. Populate the nextRight pointer in each node.*/
package BST;
public class PopulateNextRight {
BST bst = new BST();
public PopulateNextRight() {
bst.createDummyBST();
bst.printBSTInOrder(bst);
populate(bst);
printLastRights(bst);
}
private void printLastRights(BST node) {
if(node == null)
return;
BST dummyNode = node;
while(dummyNode != null) {
System.out.print(dummyNode.data + " ");
dummyNode = dummyNode.nextRight;
}
System.out.println();
printLastRights(node.left);
printLastRights(node.right);
}
public void populate(BST node){
if(node == null) {
return;
}
if(node.right !=null && node.left !=null) {
node.left.nextRight = node.right;
assignNextRight(node.right,node.nextRight);
}
else if(node.right !=null) {
assignNextRight(node.right,node.nextRight);
}
else if(node.left !=null){
assignNextRight(node.left,node.nextRight);
}
populate(node.left);
populate(node.right);
}
void assignNextRight(BST node, BST uncle){
if(uncle == null)
return;
if(uncle.left !=null)
node.nextRight = uncle.left;
else if(uncle.right !=null)
node.nextRight = uncle.right;
else
assignNextRight(node, uncle.nextRight);
}
}
/*just putting in a bit of logic: root(left, right/*ignore everything on the left, and start on the right side*/)*/
public class Node {
Node left;//left node
Node right;//right node;
int Value;
public Node(int a){
Value = a;
left = null;
right = null;
}
public void add(int a){
if(a > Value){
if(right == null)
right = new Node(a);
else
right.add(a);//recursive call
}else{
/*this would mean that the node is smaller than the root value
* and would thus be added to the left.But that's not part of the question
*/
}
}
}
A simple inorder traverse:
static void populateNextRight(BinaryNode node, BinaryNode parent)
{
if(node != null)
{
populateNextRight(node.left, node);
if(parent != null && node != parent.right)
{
node.nextRight = parent.right;
}
populateNextRight(node.right, node);
}
}
static class BinaryNode
{
int data;
BinaryNode left;
BinaryNode right;
BinaryNode nextRight;
BinaryNode(int data)
{
this.data = data;
}
}
Here is mine :
Class Node {
int value;
Node nextRight;
Node left;
Node right;
}
void fillNextRight (Node root) {
if (root == null)
return;
Node current = root;
Node nextLevelStart = root;
while (nextLevelStart != null) {
current = nextLevelStart;
nextLevelStart = null;
Node nextLevelLast = null;
while (current != null) {
fillValues( nextLevelStart, nextLevelLast, current.left);
fillValues( nextLevelStart, nextLevelLast, current.right);
current=current.nextRight;
}
}
}
void fillValues (Node nextLevelStart,Node nextLevelLast, Node nextLevelCurrent) {
if (nextLevelCurrent != null) {
if (nextLevelStart == null) nextLevelStart == nextLevelCurrent;
if (nextLevelLast != null) {
nextLevelLast.rightNode = nextLevelCurrent;
}
nextLevelLast = nextLevelCurrent;
}
}
public class NextNode{
public static class Tree<T> {
T data;
Tree<T> left;
Tree<T> right;
Tree<T> rightNode;
public Tree(T data) {
this.data = data;
}
}
static int count = 0;
public static void populateRight(Tree<Integer> t, Tree<Integer>[] ar) {
if(t == null) return;
populateRight(t.left, ar);
ar[count] = t;
count++;
populateRight(t.right, ar);
ar[count] = null;
}
public static void populateRt(Tree<Integer> t, Tree<Integer>[] ar) {
for(int i = 0; ar[i] != null; i++){
ar[i].rightNode = ar[i+1];
}
}
public static void main(String[] args) {
Tree<Integer> t = new Tree<Integer>(1);
Tree<Integer> t1 = new Tree<Integer>(2);
Tree<Integer> t2 = new Tree<Integer>(3);
Tree<Integer> t3 = new Tree<Integer>(4);
Tree<Integer> t4 = new Tree<Integer>(5);
Tree<Integer> t5 = new Tree<Integer>(6);
Tree<Integer> t6 = new Tree<Integer>(7);
t.left = t1;
t.right = t2;
t1.left = t3;
t1.right = t4;
t2.left = t5;
t2.right = t6;
//populate tree;
Tree<Integer>[] ar = new Tree[10];
populateRight(t, ar);
populateRt(t, ar);
System.out.println(t);
}
}
struct Node
{
Node *Left;
Node *Right;
Node *NextRight;
};
typedef Node* PTR;
void F(PTR &Q1, PTR &Q2)
{
Node * C2 = NULL;
while(NULL != Q1)
{
if(NULL != Q1->Left)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Left;
}
C2 = Q1->Left;
}
if(NULL != Q1->Right)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Right;
}
C2 = Q1->Right;
}
Q1 = Q1->NextRight;
}
}
struct Node
{
Node *Left;
Node *Right;
Node *NextRight;
};
typedef Node* PTR;
void F(PTR &Q1, PTR &Q2)
{
Node * C2 = NULL;
while(NULL != Q1)
{
if(NULL != Q1->Left)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Left;
}
C2 = Q1->Left;
}
if(NULL != Q1->Right)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Right;
}
C2 = Q1->Right;
}
Q1 = Q1->NextRight;
}
}
void Sibling(Node *T)
{
if(NULL != T)
{
Node *Q1 = T;
Node *Q2 = NULL;
while(NULL != Q1 || NULL != Q2)
{
F(Q1, Q2);
F(Q2, Q1);
}
}
}
I did it by doing the inorder traversal of the node and keeping track of the last visited node. The last visited node connected to the next pointer. Not sure if this is correct.
Class Node {
Node left;
Node right;
Node nextRight;
}
void updateNextRight(Node root) {
Node lastVisited = null;
updateNextRightPointers( root, lastVisited );
}
void updateNextRightPointers( Node node, Node lastVisited) {
if( node == null ) return;
updateNextRightPointers(node.left,lastVisited);
if(lastVisited != null) {
lastVisited.nextRight = root;
}
lastVisited = root;
updateNextRightPointers( node.right, lastVisited);
}
1) Store the tree in an array by using modified BreadthFirstSearch(but dont remove any node from the array).
- dhineshkumar007 January 07, 2013So the tree {1
2 3
4 5 6}
will be stored as 1 * 2 3* 4 5 6*.
2) Now in the array if the element is not '*' make its rightnode as the next element in the array, if the next element is '*' assign 'NULL.