NVIDIA Interview Question
Software Engineer InternsCountry: United States
Node* mirrorTree( Node *node )
{
if (node == NULL)
return NULL;
Node *newNode = new Node();
newNode->value = node->value;
newNode->left = mirrorTree( node->right );
newNode->right = mirrorTree(node->left);
return newNode;
}
Use pre-order traversal
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
explicit TreeNode(int v):val(v),left(NULL),right(NULL){}
};
static void pre_order(TreeNode *root, TreeNode **node) {
if (root == NULL) {
return ;
}
*node = new TreeNode(root->val);
pre_order(root->left, &((*node)->right));
pre_order(root->right, &((*node)->left));
}
TreeNode *copy_mirrorly(TreeNode *root) {
if (root == NULL) {
return NULL;
}
TreeNode *node = NULL;
pre_order(root, &node);
return node;
}
static void pre_order_print_and_free(const TreeNode *root) {
if (root == NULL) {
return ;
}
cout << root->val << endl;
TreeNode *left = root->left, *right = root->right;
delete root;
pre_order_print_and_free(left);
pre_order_print_and_free(right);
}
int main() {
TreeNode root(1), node1(2), node2(3), node3(4);
root.left = &node1;
root.right = &node2;
node1.left = &node3;
TreeNode *newL = copy_mirrorly(&root);
pre_order_print_and_free(newL);
return 0;
}
1) For each node in the tree count the no of nodes in the left subtree (k).
2) Store all elements in an array (A) and sort them
3) The root node of the BST will have the same number nodes in the left subtree as the one in the original tree. So use the count of root to find the element that will form the root of BST e.g. if left count is k then root of BST is A[k]
4) Recursively do this for the left and right subtree
Space complexity O(n)
Time complexity O(nlogn)
void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
node* mirrorBST(node *bst1 , node *bst2)
{
if(bst1 != NULL)
{
bst2 = (node*)malloc(sizeof(node));
bst2->val = bst1->val;
bst2->left = NULL;
bst2->right = NULL;
//printf("v = %d\n",root2->val );
bst2->right = mirrorBST(bst1->left,bst2->right);
bst2->left = mirrorBST(bst1->right,bst2->left);
return bst2;
}
else
{
return NULL;
}
}
struct Node {
struct Node* left;
struct Node* right;
int val;
}
typedef struct Node* Node;
Node mirror(Node root) {
if (root == NULL) return NULL;
Node result = malloc(sizeof(struct Node));
result->left = mirror(root->right);
result->right = mirror(root->left);
result->val = root->val;
return result;
}
void mirror(struct node *tree1)
{
struct node *temp;
if(tree1!=NULL)
{
temp=tree1->left;
tree1->left=tree1->right;
tree1->right=temp;
mirror(tree1->left);
mirror(tree1->right);
}
}
// where =>struct node
{
struct node *left;
int no;
struct node *right;
}
//
and (struct node *tree1) recevied the address of root node of tree.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void *print_message_function( void *ptr );
void *print_message_function2( void *ptr );
pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition_var = PTHREAD_COND_INITIALIZER;
pthread_cond_t condition_var1 = PTHREAD_COND_INITIALIZER;
int count = 10;
int main()
{
pthread_t thread1, thread2;
const char *message1 = "Thread 1";
const char *message2 = "Thread 2";
int iret1, iret2;
/* Create independent threads each of which will execute function */
iret1 = pthread_create( &thread1, NULL, print_message_function, (void*) message1);
if(iret1)
{
fprintf(stderr,"Error - pthread_create() return code: %d\n",iret1);
exit(EXIT_FAILURE);
}
iret2 = pthread_create( &thread2, NULL, print_message_function2, (void*) message2);
if(iret2)
{
fprintf(stderr,"Error - pthread_create() return code: %d\n",iret2);
exit(EXIT_FAILURE);
}
printf("pthread_create() for thread 1 returns: %d\n",iret1);
printf("pthread_create() for thread 2 returns: %d\n",iret2);
/* Wait till threads are complete before main continues. Unless we */
/* wait we run the risk of executing an exit which will terminate */
/* the process and all threads before the threads have completed. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
exit(EXIT_SUCCESS);
}
void *print_message_function( void *ptr )
{
char *message;
message = (char *) ptr;
while(count > 0){
pthread_mutex_lock( &count_mutex );
printf("Count --- %d, message--- %s\n",(10 - count), message);
count--;
pthread_cond_signal( &condition_var1 );
pthread_cond_wait( &condition_var, &count_mutex );
pthread_mutex_unlock( &count_mutex );
}
pthread_cond_signal( &condition_var1 );
}
void *print_message_function2( void *ptr )
{
char *message;
message = (char *) ptr;
while(count > 0){
pthread_mutex_lock( &count_mutex );
printf("Count --- %d, message--- %s\n",(10 - count), message);
count--;
pthread_cond_signal( &condition_var );
pthread_cond_wait( &condition_var1, &count_mutex );
pthread_mutex_unlock( &count_mutex );
}
pthread_cond_signal( &condition_var );
}
Using recursion is quite simple, just allocate a new node and recursively set the left and right children inverting them.
My C is a little rusty, but this is a complete implementation of the mirroring so you can fully understand the structure and debug it:
#include<stdio.h>
typedef struct Node
{
int value;
struct Node* left;
struct Node* right;
} Node;
void print(Node* node)
{
if (!node) return;
print(node->left);
printf("%d ", node->value);
print(node->right);
}
Node* mirror(Node* node)
{
if (!node) return NULL;
Node* newNode = malloc(sizeof(Node));
newNode->value = node->value;
newNode->left = mirror(node->right);
newNode->right = mirror(node->left);
return newNode;
}
void freeTree(Node* node)
{
if (!node) return;
freeTree(node->left);
freeTree(node->right);
free(node);
}
int main(void)
{
Node left = {.value = 2, .left = NULL, .right = NULL};
Node right = {.value = 3, .left = NULL, .right = NULL};
Node root = {.value = 1, .left = &left, .right = &right};
print(&root);
printf("\n");
Node* mirrorTree = mirror(&root);
print(mirrorTree);
printf("\n");
freeTree(mirrorTree);
return 0;
}
void mirror(struct node* node) {
- mail.anzar March 10, 2014if (node==NULL) {
return;
}
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}