using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

            ListFromTree2 obj = new ListFromTree2();

            obj.Run();

    }

}

​

​

    public class ListFromTree2

    {

​

        public static Node generalNode = new Node();

        public Node prevNode = generalNode;

​

        public void Run() {

            Node tree = createTree();

​

            KeyValuePair<Node, Node> result = FlatTree(tree, null);

​

        }

​

        public KeyValuePair<Node,Node> FlatTree(Node node, Node parent) {

            if (node.Left == null && node.Right == null) {

                return new KeyValuePair<Node,Node>(node, node);

            }

            KeyValuePair<Node, Node> leftNode = FlatTree(node.Left, node);

            KeyValuePair<Node, Node> rightNode = FlatTree(node.Right, node);

​

            leftNode.Value.Right = node;

            node.Left = null;

​

            if (parent == null)

                node.Right = rightNode.Key;

​

            KeyValuePair<Node, Node> result = new KeyValuePair<Node, Node>(leftNode.Key, rightNode.Value);

​

​

            return result;         

​

        }

​

​

        //Helpers

        public Node createTree() {

            return new Node()

            {

                Data = 20,

                Left = new Node()

                {

                    Data = 15,

                    Left = new Node

                    {

                        Data = 13,

                        Left = new Node() {

                            Data = 12

                        },

                                                Right = new Node()

                                                {

                                                    Data = 14

                                                }

​

                    },

                    Right = new Node

                    {

                        Data = 16

                    }

                },

                Right = new Node

                {

                    Data = 25,

                    Left = new Node()

                    {

                        Data = 23

                    },

                    Right = new Node()

                    {

                        Data = 26

                    }

                }

​

            };

        }

    }

​

    public class Node {

        public Node Left;

        public Node Right;

        public int Data;

    }