2
\$\begingroup\$

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.

enter image description here

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

    }
}
\$\endgroup\$
2
\$\begingroup\$

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

  }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thank you as always. This will be o(H) i kike it \$\endgroup\$ – Gilad Apr 10 '20 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.