Convert binary tree to doubly linked list

Question

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

Answer 1

Naming

• I personally prefer a class named Convert for such a task. This would also be more natural because the NET provided converting methods live in a Convert class too.
• to be consistent with the NET naming I also would prefer the method be named ToDoubleLinkedListNode()
• instead of shortening the name of the node to be returned to res, name it convertedNode
• you should name the node which is returned by the recursive calls leftNode or rightNode.

General

• by extracting the search for the last Next node which is not null to a separate method, the if..else if..else can be removed.

• if you use a guard claus for root.Right == null you save horizontal spacing.

• the method should be static, because it doesn't depend on any internal state of the class itself. This makes the constructor obsolete.

Refactoring

After all for above is applied the refactored code looks like

public class Convert
{
 public DoubleLinkedListNode ToDoubleLinkedListNode(TreeNode root)
 {
 if (root == null) { return null; }
 DoubleLinkedListNode convertedNode = new DoubleLinkedListNode { Index = root.Index };
 if (root.Left != null)
 {
 var leftNode = ToDoubleLinkedListNode(root.Left);
 leftNode.Previous = convertedNode;
 convertedNode.Next = leftNode;
 }
 if (root.Right == null) { return convertedNode; }
 var rightNode = ToDoubleLinkedListNode(root.Right);
 DoubleLinkedListNode lastNextNode = FindLastNextNode(convertedNode);
 rightNode.Previous = lastNextNode;
 lastNextNode.Next = rightNode;
 return convertedNode;
 }
 private static DoubleLinkedListNode FindLastNextNode(DoubleLinkedListNode node)
 {
 while (node.Next != null)
 {
 node = node.Next;
 }
 return node;
 }
}