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