LeetCode: Increasing Order Search Tree C#

Question

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
{
    /// <summary>
    /// https://leetcode.com/problems/increasing-order-search-tree/
    /// </summary>
    [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<int> vals = new List<int>();
            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<int> vals)
        {
            if (root == null)
            {
                return;
            }
            InOrder(root.left, vals);
            vals.Add(root.val);
            InOrder(root.right, vals);
        }

    }
}

Answer 1

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);
    }

  }