[LeetCode] Longest ZigZag Path in a Binary Tree

Problem: You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Example:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Input: root = [1]
Output: 0

Approach: We can use pre order traversal here. At every node we have two choices:

1. We can go to opposite direction i.e. if the current direction is left that is we have visited a left child, we can go to child of opposite direction which is right child of current node and we can increment the current path length. Same for right direction child too where we can go to left childe and increment the current path length.
2. We can go to same direction child and make current path length as 0 so that we can calculate the path length with root as current node.

In the end we can take maximum of above two lengths and that will be our answer.

Implementation in C#:

    public int LongestZigZag(TreeNode root)

    {

        if (root == null)

        {

            return 0;

        }

        return Math.Max(this.LongestZigZagPath(root.left, 0, true),

                        this.LongestZigZagPath(root.right, 0, false));

    }

    private int LongestZigZagPath(TreeNode node,

                                   int currPathLen,

                                   bool isLeft)

    {

        if (node == null)

        {

            return currPathLen;

        }

        return Math.Max(this.LongestZigZagPath(node.left,

                                               isLeft ? 0 : currPathLen + 1,

                                               true),

                        this.LongestZigZagPath(node.right,

                                               isLeft ? currPathLen + 1 : 0,

                                               false));

    }

Compexity: O(n)