Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Trees Interview Questions

Maximum Turns

Harsh

Last Updated on March 23, 2022 by Ria Pathak

Concepts Used

DFS , Recursion

Difficulty Level

Hard

Problem Statement :

Given a binary tree, find the path length having maximum number of bends.

See original problem statement here

Solution Approach :

Introduction :

Bend indicates switching from left to right or vice versa while traversing in the tree.
For example, consider below paths (L means moving leftwards, R means moving rightwards):

LLRRRR – 1 Bend

RLLLRR – 2 Bends

LRLRLR – 5 Bends

Approach :

The idea is to traverse left and right subtrees of the root for each node. While traversing, we will keep track of the direction (left or right). Whenever, direction changes from left to right or right to left, increment the number of turns by 1.

On reaching the leaf node, compare the number of turns with the maximum number of turns (i.e. maxBends) seen so far in a root-to-leaf path. If the number of turns in the current path is greater than the maxBends, then update the maxBends in the current path and also update the maximum path length (i.e. len) of the current path.

Complexity Analysis :

Since we are traversing each node atmost once, time complexity of this approach is O(n).

SOLUTIONS:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <stdio.h>
#include<stdlib.h>
#define ll long long
#define REP(i, n) for (i = 0; i < n; i++)
struct nodelist
{
ll value;
struct nodelist *left;
struct nodelist *right;
};
typedef struct nodelist node;
struct Queue
{
int front, rear, size;
unsigned capacity;
node* *array;
};
typedef struct Queue queue;
queue* createQueue(unsigned capacity)
{
queue* qu =(queue*)malloc(sizeof(queue));
qu->capacity = capacity;
qu->front = qu->size =0;
qu->rear = capacity-1;
qu->array = (node **)malloc(qu->capacity * sizeof(node));
return qu;
}
int isFull(queue* queue1)
{
return (queue1->size == queue1->capacity);
}
int isEmpty(queue* queue1)
{
return (queue1->size==0);
}
void enqueue(queue* queue1, node* item)
{
if(isFull(queue1))
return ;
queue1->rear = (queue1->rear +1 )%queue1->capacity;
queue1->array[queue1->rear] = item;
queue1->size = queue1->size +1;
}
node dequeue(queue* queue1)
{
node* item = queue1->array[queue1->front];
queue1->front = (queue1->front +1)%queue1->capacity;
queue1->size = queue1->size -1;
return *item;
}
node* front(queue* queue1)
{
return queue1->array[queue1->front];
}
node* rear(queue * queue1)
{
return queue1->array[queue1->rear];
}
node *createNode(ll value)
{
node *t= (node *) malloc(sizeof(node));
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node*t)
{
free(t);
}
node *replaceNegativeOne(node *root)
{
if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
void deleteTree(node *node1)
{
if(node1==NULL)
return;
deleteTree(node1->left);
deleteTree(node1->right);
free(node1);
}
node *createTreeByLevelTree()
{
ll n,m;
queue* queue1 = createQueue(100000);
node *root, *t;
root = NULL;
while(scanf("%lld", &n))
{
if(isEmpty(queue1))
{
root= createNode(n);
enqueue(queue1,root);
continue;
}
scanf("%lld", &m);
t = front(queue1);
dequeue(queue1);
t->left =createNode(n);
t->right=createNode(m);
if(t->left->value !=-1)
enqueue(queue1,t->left);
if(t->right->value !=-1)
enqueue(queue1,t->right);
if(isEmpty(queue1))
break;
}
return root;
}
void findMaxBendsUtil(node* node,
char dir, int bends,
int* maxBends, int soFar,
int* len)
{
// Base Case
if (node == NULL)
return;
// Leaf node
if (node->left == NULL && node->right == NULL) {
if (bends > *maxBends) {
*maxBends = bends;
*len = soFar;
}
}
// Recurring for both left and right child
else {
if (dir == 'l') {
findMaxBendsUtil(node->left, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->right, 'r',
bends + 1, maxBends,
soFar + 1, len);
}
else {
findMaxBendsUtil(node->right, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->left, 'l',
bends + 1, maxBends,
soFar + 1, len);
}
}
}
int findTurnCount(node* node)
{
//write your code here
if (node == NULL)
return 0;
int len = 0, bends = 0, maxBends = -1;
// Call for left subtree of the root
if (node->left)
findMaxBendsUtil(node->left, 'l',
bends, &maxBends, 1, &len);
// Call for right subtree of the root
if (node->right)
findMaxBendsUtil(node->right, 'r', bends,
&maxBends, 1, &len);
// Include the root node as well in the path length
len++;
return maxBends;
}
int main() {
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
printf("%d\n", findTurnCount(root));
deleteTree(root);
return 0;
}
</stdlib.h></stdio.h>
#include <stdio.h> #include<stdlib.h> #define ll long long #define REP(i, n) for (i = 0; i < n; i++) struct nodelist { ll value; struct nodelist *left; struct nodelist *right; }; typedef struct nodelist node; struct Queue { int front, rear, size; unsigned capacity; node* *array; }; typedef struct Queue queue; queue* createQueue(unsigned capacity) { queue* qu =(queue*)malloc(sizeof(queue)); qu->capacity = capacity; qu->front = qu->size =0; qu->rear = capacity-1; qu->array = (node **)malloc(qu->capacity * sizeof(node)); return qu; } int isFull(queue* queue1) { return (queue1->size == queue1->capacity); } int isEmpty(queue* queue1) { return (queue1->size==0); } void enqueue(queue* queue1, node* item) { if(isFull(queue1)) return ; queue1->rear = (queue1->rear +1 )%queue1->capacity; queue1->array[queue1->rear] = item; queue1->size = queue1->size +1; } node dequeue(queue* queue1) { node* item = queue1->array[queue1->front]; queue1->front = (queue1->front +1)%queue1->capacity; queue1->size = queue1->size -1; return *item; } node* front(queue* queue1) { return queue1->array[queue1->front]; } node* rear(queue * queue1) { return queue1->array[queue1->rear]; } node *createNode(ll value) { node *t= (node *) malloc(sizeof(node)); t->value = value; t->right = t->left = NULL; return t; } void deleteNode(node*t) { free(t); } node *replaceNegativeOne(node *root) { if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL)) return NULL; root->left = replaceNegativeOne(root->left); root->right = replaceNegativeOne(root->right); return root; } void deleteTree(node *node1) { if(node1==NULL) return; deleteTree(node1->left); deleteTree(node1->right); free(node1); } node *createTreeByLevelTree() { ll n,m; queue* queue1 = createQueue(100000); node *root, *t; root = NULL; while(scanf("%lld", &n)) { if(isEmpty(queue1)) { root= createNode(n); enqueue(queue1,root); continue; } scanf("%lld", &m); t = front(queue1); dequeue(queue1); t->left =createNode(n); t->right=createNode(m); if(t->left->value !=-1) enqueue(queue1,t->left); if(t->right->value !=-1) enqueue(queue1,t->right); if(isEmpty(queue1)) break; } return root; } void findMaxBendsUtil(node* node, char dir, int bends, int* maxBends, int soFar, int* len) { // Base Case if (node == NULL) return; // Leaf node if (node->left == NULL && node->right == NULL) { if (bends > *maxBends) { *maxBends = bends; *len = soFar; } } // Recurring for both left and right child else { if (dir == 'l') { findMaxBendsUtil(node->left, dir, bends, maxBends, soFar + 1, len); findMaxBendsUtil(node->right, 'r', bends + 1, maxBends, soFar + 1, len); } else { findMaxBendsUtil(node->right, dir, bends, maxBends, soFar + 1, len); findMaxBendsUtil(node->left, 'l', bends + 1, maxBends, soFar + 1, len); } } } int findTurnCount(node* node) { //write your code here if (node == NULL) return 0; int len = 0, bends = 0, maxBends = -1; // Call for left subtree of the root if (node->left) findMaxBendsUtil(node->left, 'l', bends, &maxBends, 1, &len); // Call for right subtree of the root if (node->right) findMaxBendsUtil(node->right, 'r', bends, &maxBends, 1, &len); // Include the root node as well in the path length len++; return maxBends; } int main() { node *root = NULL; root = createTreeByLevelTree(); root = replaceNegativeOne(root); printf("%d\n", findTurnCount(root)); deleteTree(root); return 0; } </stdlib.h></stdio.h>
#include 

#include

#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)



struct nodelist

{

    ll value;

    struct nodelist *left;

    struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    node* *array;

};

typedef struct Queue queue;



queue* createQueue(unsigned capacity)

{

    queue* qu =(queue*)malloc(sizeof(queue));

    qu->capacity = capacity;

    qu->front = qu->size =0;

    qu->rear = capacity-1;

    qu->array = (node **)malloc(qu->capacity * sizeof(node));

    return qu;

}



int isFull(queue*  queue1)

{

    return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

    return (queue1->size==0);

}



void enqueue(queue* queue1, node* item)

{

    if(isFull(queue1))

        return ;

    queue1->rear = (queue1->rear +1 )%queue1->capacity;

    queue1->array[queue1->rear] = item;

    queue1->size = queue1->size +1;



}



node dequeue(queue* queue1)

{

    node* item = queue1->array[queue1->front];

    queue1->front = (queue1->front +1)%queue1->capacity;

    queue1->size = queue1->size -1;

    return *item;

}



node* front(queue* queue1)

{

    return queue1->array[queue1->front];

}



node* rear(queue * queue1)

{

    return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

    node *t= (node *) malloc(sizeof(node));

    t->value = value;

    t->right = t->left = NULL;

    return  t;

}

void deleteNode(node*t)

{

    free(t);

}



node *replaceNegativeOne(node *root)

{

    if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



void deleteTree(node *node1)

{

    if(node1==NULL)

        return;

    deleteTree(node1->left);

    deleteTree(node1->right);

    free(node1);

}

node *createTreeByLevelTree()

{

    ll n,m;

    queue* queue1 = createQueue(100000);

    node *root, *t;

    root = NULL;

    while(scanf("%lld", &n))

    {

        if(isEmpty(queue1))

        {

            root= createNode(n);

            enqueue(queue1,root);

            continue;

        }

        scanf("%lld", &m);

        t = front(queue1);

        dequeue(queue1);

        t->left =createNode(n);

        t->right=createNode(m);

        if(t->left->value !=-1)

            enqueue(queue1,t->left);

        if(t->right->value !=-1)

            enqueue(queue1,t->right);



        if(isEmpty(queue1))

            break;

    }

    return root;

}



void findMaxBendsUtil(node* node,

                      char dir, int bends,

                      int* maxBends, int soFar,

                      int* len)

{

    // Base Case

    if (node == NULL)

        return;



    // Leaf node

    if (node->left == NULL && node->right == NULL) {

        if (bends > *maxBends) {

            *maxBends = bends;

            *len = soFar;

        }

    }

        // Recurring for both left and right child

    else {

        if (dir == 'l') {

            findMaxBendsUtil(node->left, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->right, 'r',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

        else {

            findMaxBendsUtil(node->right, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->left, 'l',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

    }

}



int findTurnCount(node* node)

{

    //write your code here

        if (node == NULL)

        return 0;



    int len = 0, bends = 0, maxBends = -1;



    // Call for left subtree of the root

    if (node->left)

        findMaxBendsUtil(node->left, 'l',

                         bends, &maxBends, 1, &len);



    // Call for right subtree of the root

    if (node->right)

        findMaxBendsUtil(node->right, 'r', bends,

                         &maxBends, 1, &len);



    // Include the root node as well in the path length

    len++;



    return maxBends;

}

int main() {

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    printf("%d\n", findTurnCount(root));

    deleteTree(root);

    return 0;



}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#define REP(i, n) for (i = 0; i < n; i++)
#define pb(a) push_back(a)
#define vi vector<long>
#define ll long long
#include <bits stdc++.h="">
using namespace std;
struct node
{
ll value;
node *left;
node *right;
};
node *createNode(ll value)
{
node *t = new node();
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node *t)
{
delete t;
}
node *replaceNegativeOne(node *root)
{
if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
node *createTreeByLevelTree()
{
ll n, m;
queue<node *=""> q;
node *root, *t;
root = NULL;
while (cin >> n)
{
if (q.empty())
{
root = createNode(n);
q.push(root);
continue;
}
cin >> m;
t = q.front();
q.pop();
t->left = createNode(n);
t->right = createNode(m);
if (t->left->value != -1)
{
q.push(t->left);
}
if (t->right->value != -1)
{
q.push(t->right);
}
if (q.empty())
{
break;
}
}
return root;
}
void deleteTree(node *node)
{
if (node == NULL)
return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
void findMaxBendsUtil(node* node,
char dir, int bends,
int* maxBends, int soFar,
int* len)
{
if (node == NULL)
return;
if (node->left == NULL && node->right == NULL) {
if (bends > *maxBends) {
*maxBends = bends;
*len = soFar;
}
}
else {
if (dir == 'l') {
findMaxBendsUtil(node->left, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->right, 'r',
bends + 1, maxBends,
soFar + 1, len);
}
else {
findMaxBendsUtil(node->right, dir,
bends, maxBends,
soFar + 1, len);
findMaxBendsUtil(node->left, 'l',
bends + 1, maxBends,
soFar + 1, len);
}
}
}
int findTurnCount(node* node)
{
//write your code here
if (node == NULL)
return 0;
int len = 0, bends = 0, maxBends = -1;
// Call for left subtree of the root
if (node->left)
findMaxBendsUtil(node->left, 'l',
bends, &maxBends, 1, &len);
// Call for right subtree of the root
if (node->right)
findMaxBendsUtil(node->right, 'r', bends,
&maxBends, 1, &len);
len++;
return maxBends;
}
int main()
{
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
cout<<findturncount(root)<<endl; deletetree(root);="" return="" 0;="" }="" <="" pre="">
<!-- /wp:enlighter/codeblock -->
</findturncount(root)<<endl;></node></bits></long>
#define REP(i, n) for (i = 0; i < n; i++) #define pb(a) push_back(a) #define vi vector<long> #define ll long long #include <bits stdc++.h=""> using namespace std; struct node { ll value; node *left; node *right; }; node *createNode(ll value) { node *t = new node(); t->value = value; t->right = t->left = NULL; return t; } void deleteNode(node *t) { delete t; } node *replaceNegativeOne(node *root) { if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL)) return NULL; root->left = replaceNegativeOne(root->left); root->right = replaceNegativeOne(root->right); return root; } node *createTreeByLevelTree() { ll n, m; queue<node *=""> q; node *root, *t; root = NULL; while (cin >> n) { if (q.empty()) { root = createNode(n); q.push(root); continue; } cin >> m; t = q.front(); q.pop(); t->left = createNode(n); t->right = createNode(m); if (t->left->value != -1) { q.push(t->left); } if (t->right->value != -1) { q.push(t->right); } if (q.empty()) { break; } } return root; } void deleteTree(node *node) { if (node == NULL) return; deleteTree(node->left); deleteTree(node->right); delete node; } void findMaxBendsUtil(node* node, char dir, int bends, int* maxBends, int soFar, int* len) { if (node == NULL) return; if (node->left == NULL && node->right == NULL) { if (bends > *maxBends) { *maxBends = bends; *len = soFar; } } else { if (dir == 'l') { findMaxBendsUtil(node->left, dir, bends, maxBends, soFar + 1, len); findMaxBendsUtil(node->right, 'r', bends + 1, maxBends, soFar + 1, len); } else { findMaxBendsUtil(node->right, dir, bends, maxBends, soFar + 1, len); findMaxBendsUtil(node->left, 'l', bends + 1, maxBends, soFar + 1, len); } } } int findTurnCount(node* node) { //write your code here if (node == NULL) return 0; int len = 0, bends = 0, maxBends = -1; // Call for left subtree of the root if (node->left) findMaxBendsUtil(node->left, 'l', bends, &maxBends, 1, &len); // Call for right subtree of the root if (node->right) findMaxBendsUtil(node->right, 'r', bends, &maxBends, 1, &len); len++; return maxBends; } int main() { node *root = NULL; root = createTreeByLevelTree(); root = replaceNegativeOne(root); cout<<findturncount(root)<<endl; deletetree(root);="" return="" 0;="" }="" <="" pre=""> <!-- /wp:enlighter/codeblock --> </findturncount(root)<<endl;></node></bits></long>
#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector

#define ll long long

#include 

using namespace std;

struct node

{

    ll value;

    node *left;

    node *right;

};



node *createNode(ll value)

{

    node *t = new node();

    t->value = value;

    t->right = t->left = NULL;

    return t;

}

void deleteNode(node *t)

{

    delete t;

}

node *replaceNegativeOne(node *root)

{

    if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

        return NULL;

    root->left = replaceNegativeOne(root->left);

    root->right = replaceNegativeOne(root->right);

    return root;

}



node *createTreeByLevelTree()

{

    ll n, m;

    queue q;



    node *root, *t;



    root = NULL;



    while (cin >> n)

    {

        if (q.empty())

        {

            root = createNode(n);

            q.push(root);

            continue;

        }

        cin >> m;



        t = q.front();

        q.pop();



        t->left = createNode(n);

        t->right = createNode(m);



        if (t->left->value != -1)

        {

            q.push(t->left);

        }



        if (t->right->value != -1)

        {

            q.push(t->right);

        }

          if (q.empty())

        {

            break;

        }

    }



    return root;

}



void deleteTree(node *node)

{

    if (node == NULL)

        return;



    deleteTree(node->left);

    deleteTree(node->right);

    delete node;

}



void findMaxBendsUtil(node* node,

                      char dir, int bends,

                      int* maxBends, int soFar,

                      int* len)

{


    if (node == NULL)

        return;


    if (node->left == NULL && node->right == NULL) {

        if (bends > *maxBends) {

            *maxBends = bends;

            *len = soFar;

        }

    }



    else {

        if (dir == 'l') {

            findMaxBendsUtil(node->left, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->right, 'r',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

        else {

            findMaxBendsUtil(node->right, dir,

                             bends, maxBends,

                             soFar + 1, len);

            findMaxBendsUtil(node->left, 'l',

                             bends + 1, maxBends,

                             soFar + 1, len);

        }

    }

}



int findTurnCount(node* node)

{

    //write your code here

        if (node == NULL)

        return 0;



    int len = 0, bends = 0, maxBends = -1;



    // Call for left subtree of the root

    if (node->left)

        findMaxBendsUtil(node->left, 'l',

                         bends, &maxBends, 1, &len);



    // Call for right subtree of the root

    if (node->right)

        findMaxBendsUtil(node->right, 'r', bends,

                         &maxBends, 1, &len);





    len++;

    return maxBends;

}

int main()

{

    node *root = NULL;

    root = createTreeByLevelTree();

    root = replaceNegativeOne(root);

    cout<

[forminator_quiz id="1721"]

This article tried to discuss DFS , Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on DFS , Recursion you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post