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!

Maximum Turns

Last Updated on March 23, 2022 by Ria Pathak

DFS , Recursion

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:

```#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)

{

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;

}
```
```#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)

{

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.