The code works and I get the results I want. Please comment about complexity, a shorter way of implementing the solution, and advice for better unit tests.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
public class BinaryTreeToList
{
public BinaryTreeToList()
{
}
public DoubleLinkedListNode ConvertTreeToDoubleLinkedListNode(TreeNode root)
{
if (root == null)
{
return null;
}
DoubleLinkedListNode res = new DoubleLinkedListNode();
res.Index = root.Index;
if (root.Left != null)
{
var newNode = ConvertTreeToDoubleLinkedListNode(root.Left);
newNode.Previous = res;
res.Next = newNode;
}
if (root.Right != null)
{
if (res.Next == null)
{
var newNode = ConvertTreeToDoubleLinkedListNode(root.Right);
newNode.Previous = res;
res.Next = newNode;
}
else if (res.Next.Next == null)
{
var newNode = ConvertTreeToDoubleLinkedListNode(root.Right);
newNode.Previous = res.Next;
res.Next.Next = newNode;
}
else
{
DoubleLinkedListNode temp = res;
while (temp.Next != null)
{
temp = temp.Next;
}
var newNode = ConvertTreeToDoubleLinkedListNode(root.Right);
newNode.Previous = temp;
temp.Next = newNode;
}
}
return res;
}
}
public class DoubleLinkedListNode
{
public int Index { get; set; }
public DoubleLinkedListNode Next { get; set; }
public DoubleLinkedListNode Previous { get; set; }
}
}
Unit Test
using System;
using System.Collections.Generic;
using ConsoleApplication2;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace UnitTests
{
[TestClass]
public class BinaryTreeConvertToList
{
[TestMethod]
public void TestMethod1()
{
BinaryTreeToList binaryTreeToList = new BinaryTreeToList();
// 0
// 2 4
// 6 8 10
TreeNode root = new TreeNode(0);
root.Left = new TreeNode(2);
root.Right = new TreeNode(4);
root.Left.Left = new TreeNode(6);
root.Left.Right = new TreeNode(8);
root.Right.Right = new TreeNode(10);
var res1 = binaryTreeToList.ConvertTreeToDoubleLinkedListNode(root);
Assert.AreEqual(0, res1);
Assert.AreEqual(2, res1.Next);
}
}
}