Leetcode discuss: 2096. Step-By-Step Directions From a Binary Tree Node to Another

March 21, 2022

Here is the link. 

C# | Post order traversal | Solve TLE problem

March 21, 2022
Introduction
It is hard for me to solve TLE problem until I came cross a few of discuss post using C# and both of them applies post order traversal, only apply path concentation string manipulation for only one working path only. I just learned the importance to avoid unnecessary work, since I prepare for Meta phone screen, and I understand that it is so important to learn to solve TLE problem.

Algorithm analysis
I just copied the analysis from votrubac, and it is important to understand the tasks:

1. Find paths to source value and dest value;
2. Find common prefix, and then source path is replaced by "U" char always
3. Dest path should be appended after removing those common prefix with source path.

Build directions for both start and destination from the root.
Say we get "LLRRL" and "LRR".
Remove common prefix path.
We remove "L", and now start direction is "LRRL", and destination - "RR"
Replace all steps in the start direction to "U" and add destination direction.
The result is "UUUU" + "RR".

Post order traversal | C# List | C# List API Insert | Bottom-up, always insert in front of the list
I just quickly made some modification of study code, and then code passes online judge.

Design requirement | check list for the player
Design requirement:
Only call C# List.Insert API for the path from root to node with val
In other words, do not build path for any other path in the binary tree. To find source node, it requires to traverse the whole tree worst case, but it only takes less than height of tree steps to build the actual path using 'L' or 'R'. Do not involve those nodes not in the path, or think about back tracking etc.

TLE error is very common in Leetcode 2096 online judge

Design recursive function with bool return value, so it is easy to check post order traversal return value; only call C# List.Insert API when the node is in the path from source node to root node, and also Insert at index position 0.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _2096_step___by___step_post_order___TLE
{
    class Program
    {
        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;
          }
        }

        static void Main(string[] args)
        {
            var node5 = new TreeNode(5);
            node5.left = new TreeNode(1);
            node5.right = new TreeNode(2);
            node5.left.left = new TreeNode(3);
            node5.right.left = new TreeNode(6);
            node5.right.right = new TreeNode(4);

            var test = new Program();
            var start = test.GetDirections(node5, 3, 6);
            //var end = test.GetDirections(node5,6, 3);
        }

        /// <summary>
        /// March 21, 2022
        /// study code
        /// https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/discuss/1613921/C-Postorder-Travesal
        /// </summary>
        /// <param name="root"></param>
        /// <param name="startValue"></param>
        /// <param name="destValue"></param>
        /// <returns></returns>
        public string GetDirections(TreeNode root, int startValue, int destValue)
        {
            if (root == null)
                return string.Empty;

            var pathStart = new List<char>();
            var pathEnd = new List<char>();

            runPostOrderTraversal(root, startValue, pathStart);
            runPostOrderTraversal(root, destValue,  pathEnd);

            while (pathStart.Count > 0 && pathEnd.Count > 0 && pathStart[0] == pathEnd[0])
            {
                pathStart.RemoveAt(0);
                pathEnd.RemoveAt(0);
            }

            var sb = new StringBuilder();
            for (int i = 0; i < pathStart.Count; i++)
            {
                sb.Append('U');
            }
            for (int i = 0; i < pathEnd.Count; i++)
            {
                sb.Append(pathEnd[i]);
            }

            return sb.ToString();
        }

        /// Conditional traversal - check return value
        /// Design requirement:
        /// Only call C# List.Insert API for the path from root to node with val
        /// In other words, do not build path for any other path in the binary tree. 
        /// TLE error is very common in Leetcode 2096 online judge 
        private bool runPostOrderTraversal(TreeNode root, int val, List<char> path)
        {
            if (root == null)
            {
                return false;
            }

            if (root.val == val)
            {
                return true;
            }

            if (runPostOrderTraversal(root.left, val, path))
            {
                path.Insert(0, 'L'); // bottom up - so insert at 0 position make sense
                return true;
            }
            else if (runPostOrderTraversal(root.right, val, path))
            {
                path.Insert(0, 'R');
                return true;
            }

            return false;
        }
    }
}