Leetcode discuss: Longest ZigZag Path in a Binary Tree

 Here is the link. 

C# preorder traversal with optimal space and time complexity

1372. Longest ZigZag Path in a Binary Tree

August 25, 2020
Introduction
It took me over 10 minutes to come out this idea better than brute force solution. The naive idea is to find all paths in the binary tree, and then search all possible zigzag paths in any path.

Better idea is to start from any node, and check it's downward path to leaf node longest zigzag path. If it is left child, then check left child only, since right child should be checked by it's parent node.

Case study
A tree with three nodes, root node with value 1, root node's left child with value 2, and root node's left child's right child with value 3.

The idea is to apply preorder traverse the tree, so the root is visited, and then check it's both directions, and downward zigzag path, only one path, from root node, go to left, and then go to right. The length is 2.

When the root node's left child is visited, only need to check it's left child downward zigzag path, which has length value 0.

Time complexity
average time complexity O(nlogn), logn is average height of tree, n is total number of nodes.
Space complexity
O(1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    /// <summary>
        /// August 25, 2020
        /// I came out two ideas. I need to come out at least two ideas before I write any code.
        /// The first one is to find all paths from root to leaf node, and then search one by one 
        /// longest zigzag path, space is not efficient, need to store all paths. 
        /// I worked on the second idea, it is to preorder traverse the tree, 
        /// for each node, check left or right zig zag path for longest one. 
        /// If it is the left child of it's parent node, do not need to check
        /// right child. Same applies to right child. 
        /// The average time complexity will be O(nlogn), n is total number of 
        /// nodes in the tree, and logn is average height of the tree. 
        /// Space complexity is O(1). No need to store all paths. 
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public int LongestZigZag(TreeNode root)
        {
            if (root == null)
                return 0;

            var longest = 0;

            preorderTraverseTree(root, 2, ref longest);

            return longest;
        }

        /// <summary>
        /// preorder traverse the tree
        /// 0 - is left child
        /// 1 - is right child
        /// 2 - not applied
        /// unit test:
        /// 1. Tree with one node - 0
        /// </summary>
        /// <param name="root"></param>
        /// <param name="longest"></param>
        private void preorderTraverseTree(TreeNode root, int directionToChild, ref int longest)
        {
            if (root == null)
                return;

            // visit current node
            if (directionToChild == 2)
            {
                // go to left and also go to right two directions to find zigzag paths
                var path1 = findDownwardZigzag(root, 0);
                longest = path1 > longest ? path1 : longest;

                var path2 = findDownwardZigzag(root, 1);
                longest = path2 > longest ? path2 : longest;
            }
            else if (directionToChild == 0)
            {
                // go to left downward zigzag                
                var path = findDownwardZigzag(root, 0);
                longest = path > longest ? path : longest;
            }
            else if (directionToChild == 1)
            {
                // go to right downward zigzag
                var path = findDownwardZigzag(root, 1);
                longest = path > longest ? path : longest;
            }            

            preorderTraverseTree(root.left,  0,  ref longest);
            preorderTraverseTree(root.right, 1,  ref longest);
        }

        private int findDownwardZigzag(TreeNode root, int direction)
        {            
            var count = direction; 
            while ((count % 2 == 0 && root != null && root.left  != null) || 
                   (count % 2 == 1 && root != null && root.right != null))
            {             

                if (count % 2 == 0)
                {
                    root = root.left;
                }
                else
                {
                    root = root.right;
                }

                count++;
            }

            return count - direction; 
        }
}