1
/ \
2 3
/\ /\
4 5 6 7
Sample output 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
c# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
class Program
{
static void Main(string[] args)
{
BinaryTreeNode b = new BinaryTreeNode();
b.Data = 1;
b.Left = new BinaryTreeNode(){Data = 2, Left = new BinaryTreeNode(){Data = 4}, Right = new BinaryTreeNode(){Data = 5}};
b.Right = new BinaryTreeNode(){Data = 3, Left = new BinaryTreeNode(){Data = 6}, Right = new BinaryTreeNode(){Data = 7}};
LinkedListNode ll = TreeToLinkedList(b);
var temp = ll;
while (temp.Previous != null)
{
temp = temp.Previous;
}
while (temp != null)
{
Console.Write(temp.Data);
Console.Write(" -> ");
temp = temp.Next;
}
}
static LinkedListNode TreeToLinkedList(BinaryTreeNode node)
{
if (node == null) return null;
var linkedListNode = new LinkedListNode {Data = node.Data};
var leftLinkedList = TreeToLinkedList(node.Left);
var rightLinkedList = TreeToLinkedList(node.Right);
//Travel to left most node
var temp = leftLinkedList;
if (temp?.Next != null)
{
temp = temp.Next;
}
linkedListNode.Previous = temp;
//Travel to right most node
temp = rightLinkedList;
if (temp?.Previous != null)
{
temp = temp.Previous;
}
linkedListNode.Next = temp;
if (linkedListNode.Previous != null)
{
linkedListNode.Previous.Next = linkedListNode;
}
if (linkedListNode.Next != null)
{
linkedListNode.Next.Previous = linkedListNode;
}
return linkedListNode;
}
}
class BinaryTreeNode
{
public int Data { get; set; }
public BinaryTreeNode Left { get; set; }
public BinaryTreeNode Right { get; set; }
}
class LinkedListNode
{
public int Data;
public LinkedListNode Previous { get; set; }
public LinkedListNode Next { get; set; }
}
}