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 in data structures and algorithms in c++.
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 <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;



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

}

Previous post LevelOrder Traversal
Next post Mirror Reflection

Leave a Reply

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