Posted on by Kalkicode
Code Binary Tree

Convert given binary tree to doubly linked list in c#

Csharp program for Convert given binary tree to doubly linked list. Here problem description and explanation.

// Include namespace system
using System;
/* 
  Csharp program for
  Convert a given binary tree to doubly linked list
*/
// Binary Tree Node
public class LinkNode
{
	public int data;
	public LinkNode left;
	public LinkNode right;
	public LinkNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public LinkNode root;
	public BinaryTree()
	{
		// Set initial values
		this.root = null;
	}
	// Display node element of doubly linked list
	public void display()
	{
		if (this.root == null)
		{
			Console.WriteLine("Empty Linked List");
		}
		else
		{
			Console.WriteLine("Linked List Head to Tail :");
			// Get first node of linked list
			var temp = this.root;
			LinkNode tail = null;
			// iterate the linked list
			while (temp != null)
			{
				tail = temp;
				// Display node value
				Console.Write("  " + temp.data);
				// Visit to next node
				temp = temp.right;
			}
			Console.WriteLine("\nLinked List Tail to Head :");
			// Get last node of linked list
			temp = tail;
			// iterate the linked list
			while (temp != null)
			{
				// Display node value
				Console.Write("  " + temp.data);
				// Visit to prev node
				temp = temp.left;
			}
		}
	}
	// Function which is convert binary tree to DLL
	public void transform(LinkNode node, LinkNode x, LinkNode y)
	{
		if (node != null)
		{
			// Visit to left subtree
			this.transform(node.left, x, node);
			if (this.root == null)
			{
				// Set the root node when is empty
				this.root = node;
			}
			// Visit to right subtree
			this.transform(node.right, node, y);
			if (node.left == null)
			{
				// Connect left node
				node.left = x;
				if (x != null)
				{
					// Connect right to left node
					x.right = node;
				}
			}
			if (node.right == null)
			{
				// Connect right node
				node.right = y;
				if (y != null)
				{
					// Connect left to right node
					y.left = node;
				}
			}
		}
	}
	public void doublyList()
	{
		var node = this.root;
		if (node != null)
		{
			// Reset the root value
			this.root = null;
			// Covert into Doubly linked list
			this.transform(node, null, null);
		}
	}
	public static void Main(String[] args)
	{
		// Create new tree
		var tree = new BinaryTree();
		/*
		  Binary Tree
		-----------------------
		        1
		       /  \
		      2    3
		     /    /  \
		    4    5    6
		     \    \
		      7    9
		     / 
		    8
		*/
		// Add binary tree nodes
		tree.root = new LinkNode(1);
		tree.root.left = new LinkNode(2);
		tree.root.right = new LinkNode(3);
		tree.root.right.right = new LinkNode(6);
		tree.root.right.left = new LinkNode(5);
		tree.root.right.left.right = new LinkNode(9);
		tree.root.left.left = new LinkNode(4);
		tree.root.left.left.right = new LinkNode(7);
		tree.root.left.left.right.left = new LinkNode(8);
		tree.doublyList();
		tree.display();
	}
}

Output

Linked List Head to Tail :
  4  8  7  2  1  5  9  3  6
Linked List Tail to Head :
  6  3  9  5  1  2  7  8  4

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment