Write a program to Convert a binary tree to doubly linked list.

Binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Wikipedia

Solution

using System;

namespace LinkedListOpearation
{
    class Program
    {
        public static void Main(string[] args)
        {
            var linkedList = new DoublyLinkedList
            {
                Root = new Node(10) {Left = new Node(12), Right = new Node(15)}
            };

            linkedList.Root.Left.Left = new Node(25);
            linkedList.Root.Left.Right = new Node(30);
            linkedList.Root.Right.Left = new Node(36);

            linkedList.ConvertBinaryTreeToLinkedList(linkedList.Root);
            linkedList.Print(linkedList.Head);
            Console.ReadLine();
        }   
    }

    class DoublyLinkedList
    {
        public Node Root;
        public Node Head;
        public static Node Prev;

        public virtual void ConvertBinaryTreeToLinkedList(Node root)
        {
            if (root == null)
                return;

            ConvertBinaryTreeToLinkedList(root.Left);

            if (Prev == null)
            {
                Head = root;
            }
            else
            {
                root.Left = Prev;
                Prev.Right = root;
            }
            Prev = root;

            ConvertBinaryTreeToLinkedList(root.Right);
        }

        public void Print(Node node)
        {
            while (node != null)
            {
                Console.WriteLine(node.Data);
                node = node.Right;
            }
        }
    }

    public class Node
    {
        public int Data;
        public Node Left;
        public Node Right;

        public Node(int data)
        {
            Data = data;
        }
    }
}