{"id":1716,"date":"2020-06-11T11:52:47","date_gmt":"2020-06-11T11:52:47","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1716"},"modified":"2022-03-23T23:43:56","modified_gmt":"2022-03-23T23:43:56","slug":"maximum-turns","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-turns\/","title":{"rendered":"Maximum Turns"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

DFS , Recursion<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a binary tree, find the path length having maximum number of bends.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Bend indicates switching from left to right or vice versa while traversing in the tree.
\nFor example, consider below paths (L means moving leftwards, R means moving rightwards):<\/p>\n

LLRRRR \u2013 1 Bend<\/p>\n

RLLLRR \u2013 2 Bends<\/p>\n

LRLRLR \u2013 5 Bends<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Approach :<\/h4>\n
\n

The idea is to traverse left<\/strong> and right<\/strong> 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<\/code>.<\/p>\n

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.<\/p>\n<\/blockquote>\n

Complexity Analysis :<\/h3>\n
\n

Since we are traversing each node atmost once, time complexity of this approach is O(n)<\/code>.<\/p>\n<\/blockquote>\n

SOLUTIONS:<\/h3>\n

\t\t\t\t\t\t