Convert a binary tree to a doubly circular linked list.

Question

Sushil · Accepted Answer

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    class TreeNode
    {
        public int Index { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
        public void InorderTraverse()
        {
            if (this.Left != null)
                this.Left.InorderTraverse();
            Console.WriteLine("tree node: {0}", this.Index);
            if (this.Right != null)
                this.Right.InorderTraverse();
        }
    }
    class ListNode
    {
        public int Index { get; set; }
        public ListNode Prev { get; set; }
        public ListNode Next { get; set; }
        public static ListNode CreateNode(int index)
        {
            var ret = new ListNode();
            ret.Index = index;
            ret.Prev = ret;
            ret.Next = ret;
            return ret;
        }
        public void Append(ListNode list)
        {
            Debug.Assert(list != null);
            Debug.Assert(list.Prev != null);
            Debug.Assert(list.Next != null);
            Debug.Assert(this.Prev != null);
            Debug.Assert(this.Next != null);
            var listLastNode = list.Prev;
            var thisLastNode = this.Prev;
            // link list last node & thislist 
            listLastNode.Next = this;
            this.Prev = listLastNode;
            // link thislist last node & list
            thisLastNode.Next = list;
            list.Prev = thisLastNode;
        }
        public void TraverseForward()
        {
            var node = this;
            do
            {
                Console.WriteLine("list node: {0}", node.Index);
                node = node.Next;
            }
            while (node != this);
        }
        public void TraverseBackward()
        {
            var node = this.Prev;
            do
            {
                Console.WriteLine("list node: {0}", node.Index);
                node = node.Prev;
            }
            while (node != this.Prev);
        }
    }
    class Program
    {
        static TreeNode BuildTree()
        {
            return new TreeNode()
            {
                Index = 4,
                Left = new TreeNode()
                {
                    Index = 2,
                    Left = new TreeNode()
                    {
                        Index = 1
                    },
                    Right = new TreeNode()
                    {
                        Index = 3
                    }
                },
                Right = new TreeNode()
                {
                    Index = 6,
                    Left = new TreeNode()
                    {
                        Index = 5
                    },
                    Right = new TreeNode()
                    {
                        Index = 7
                    }
                },
            };
        }

        static ListNode ConvertToList(TreeNode root)
        {
            // convert to list with inorder traversal
            if (root == null)
                return null;
            ListNode result;
            var thisNode = ListNode.CreateNode(root.Index);
            if (root.Left != null)
            {
                result = ConvertToList(root.Left);
                result.Append(thisNode);
            }
            else
                result = thisNode;
            if (root.Right != null)
            {
                var rightList = ConvertToList(root.Right);
                result.Append(rightList);
            }
            return result;
        }

        static void Main(string[] args)
        {
            var root = BuildTree();
            Console.WriteLine("Tree inoder traversal::");
            root.InorderTraverse();
            var list = ConvertToList(root);
            Console.WriteLine("List forward traversal::");
            list.TraverseForward();
            Console.WriteLine("List backward traversal::");
            list.TraverseBackward();
        }
    }
}

sravan · Answer

Convert the binary tree into threaded binary tree and then just modify the prev and next pointers such that it will become double linked list

Gilad Darmon · Answer

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

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches