LeetCode: Increasing Order Search Tree C# https://leetcode.com/problems/increasing-order-search-tree/

Please review for performance


  Given a binary search tree, rearrange the tree in in-order so that the
  leftmost node in the tree is now the root of the tree, and every node
  has no left child and only 1 right child.





  Constraints:
  
  The number of nodes in the given tree will be between 1 and 100. Each
  node will have a unique integer value from 0 to 1000.


using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/problems/increasing-order-search-tree/
    /// &lt;/summary&gt;
    [TestClass]
    public class IncreasingBstTest
    {
        [TestMethod]
        public void ExampleTest()
        {

                //      5
                //     / \
                //    3   6
                //   / \   \
                //  2   4   8
                // /      / \
                // 1     7   9

            TreeNode root = new TreeNode(5);
            root.left = new TreeNode(3);
            root.left.left = new TreeNode(2);
            root.left.right = new TreeNode(4);
            root.left.left.left = new TreeNode(1);

            root.right = new TreeNode(6);
            root.right.right = new TreeNode(8);
            root.right.right.left = new TreeNode(7);
            root.right.right.right = new TreeNode(9);
            var forEach = new InOrderForEach();
            root = forEach.IncreasingBST(root);

            int res = 1;
            var curr = root;
            while (curr != null)
            {
                Assert.AreEqual(res, curr.val);
                curr = curr.right;
                res++;
            }
        }
    }


    }

    public class InOrderForEach
    {
        public TreeNode IncreasingBST(TreeNode root)
        {
            if (root == null)
            {
                return null;
            }
            List&lt;int&gt; vals = new List&lt;int&gt;();
            InOrder(root, vals);
            var ans = new TreeNode(0);
            TreeNode curr = ans;
            foreach (var v in vals)
            {
                curr.right = new TreeNode(v);
                curr = curr.right;
            }
            return ans.right;
        }

        private void InOrder(TreeNode root, List&lt;int&gt; vals)
        {
            if (root == null)
            {
                return;
            }
            InOrder(root.left, vals);
            vals.Add(root.val);
            InOrder(root.right, vals);
        }

    }
}
There isn't much to review. InOrder() is merely a depth-first-search, so maybe I would call it that.

You could though optimize a bit, if you created the new "tree" as you traverse the old one:

  public class InOrderForEach
  {
    TreeNode newRoot = new TreeNode(0);
    TreeNode current = null;

    public TreeNode IncreasingBST(TreeNode root)
    {
      if (root == null)
      {
        return null;
      }
      current = newRoot;
      InOrder(root);
      return newRoot.right;
    }

    private void InOrder(TreeNode root)
    {
      if (root == null)
      {
        return;
      }
      InOrder(root.left);
      current = current.right = new TreeNode(root.val);
      InOrder(root.right);
    }

  }