Trees Interview Questions | Maximum Turns

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:

#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;



}

#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.

Maximum Turns

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Approach :

Complexity Analysis :

SOLUTIONS:

Leave a Reply Cancel reply

Difference between Big Oh, Big Omega, and Big Theta

Basics of Analysis of Algorithms

Types of Algorithm Analysis

Why Analysis of Algorithms is important?

What is meant by Algorithm Analysis?

Design and Analysis of Algorithms

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Approach :

Complexity Analysis :

SOLUTIONS:

Leave a Reply Cancel reply