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

March 21, 2022

Here is the link. 

C# | Preorder | TLE error 287/332

March 21, 2022
Introduction
It took me over 30 minutes to work on a few issues, and then my algorithm could not pass online judge, failed test case 287/332 TLE error.

Preorder traversal | Find startValue and DestValue | Common prefix

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

namespace _2096_step_by_step
{
    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,3, 6);
        }

        /// <summary>
        /// Find startValue using 'L','R','U'
        /// Find endValue using 'L','R','U'
        /// </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 "";

            var found = false;
            var found2 = false;
            var path1 = new StringBuilder();
            var path2 = new StringBuilder();
            
            runPreOrderTraversal(root, startValue, ref found, "", path1);
            runPreOrderTraversal(root, destValue, ref found2, "", path2);
            var commonPrefix = -1;

            for (int i = 0; i < Math.Min(path1.Length, path2.Length); i++)
            {
                if (path1[i] == path2[i])
                {
                    commonPrefix = i;
                    continue;
                }
                else
                {
                    break;
                }
            }

            var result = new StringBuilder();
            var start = commonPrefix + 1;
            while (start < path1.Length)
            {
                result.Append('U');
                start++;
            }

            start = commonPrefix + 1;
            while (start < path2.Length)
            {
                result.Append(path2[start]);
                start++;
            }

            return result.ToString();
        }

        private void runPreOrderTraversal(TreeNode root, int startValue, ref bool found, string prefix, StringBuilder path)
        {
            if (root == null || found)
            {                
                return;
            }

            if (root.val == startValue)
            {
                found = true;
                foreach(var item in prefix)
                    path.Append(item);
                return;
            }
            
            runPreOrderTraversal(root.left,  startValue, ref found, prefix + "L", path);            
            runPreOrderTraversal(root.right, startValue, ref found, prefix + "R", path);
            
        }
    }
}