CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to convert a given binary tree to doubly linked list.ExplanationIn this program, we need to convert the given binary tree to corresponding doubly liked list. The binary tree is a tree data structure in which each node has at most two children node. This can be achieved by traversing the tree in the inorder manner that is, left the child > root >right node. Traverse left subtree and convert it into the doubly linked list by adding nodes to the end of the list. In this way, leftmost node will become head of the list. Then, convert the right subtree into the doubly linked list. Binary tree: Corresponding doubly linked list: Algorithm
SolutionPython#Represent a node of binary tree class Node: def __init__(self,data): self.data = data; self.left = None; self.right = None; class BinaryTreeToDLL: def __init__(self): #Represent the root of binary tree self.root = None; #Represent the head and tail of the doubly linked list self.head = None; self.tail = None; #convertbtToDLL() will convert the given binary tree to corresponding doubly linked list def convertbtToDLL(self, node): #Checks whether node is None if(node == None): return; #Convert left subtree to doubly linked list self.convertbtToDLL(node.left); #If list is empty, add node as head of the list if(self.head == None): #Both head and tail will point to node self.head = self.tail = node; #Otherwise, add node to the end of the list else: #node will be added after tail such that tail's right will point to node self.tail.right = node; #node's left will point to tail node.left = self.tail; #node will become new tail self.tail = node; #Convert right subtree to doubly linked list self.convertbtToDLL(node.right); #display() will print out the nodes of the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print("List is empty"); return; print("Nodes of generated doubly linked list: "); while(current != None): #Prints each node by incrementing pointer. print(current.data), current = current.right; bt = BinaryTreeToDLL(); #Add nodes to the binary tree bt.root = Node(1); bt.root.left = Node(2); bt.root.right = Node(3); bt.root.left.left = Node(4); bt.root.left.right = Node(5); bt.root.right.left = Node(6); bt.root.right.right = Node(7); #Converts the given binary tree to doubly linked list bt.convertbtToDLL(bt.root); #Displays the nodes present in the list bt.display(); Output: Nodes of generated doubly linked list: 4 2 5 1 6 3 7 C#include <stdio.h> //Represent a node of the binary tree struct node{ int data; struct node *left; struct node *right; }; //Represent the root of the binary tree struct node *root; //Represent the head and tail of the doubly linked list struct node *head, *tail = NULL; //createNode() will create a new node struct node* createNode(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Assign data to newNode, set left and right child to NULL newNode>data = data; newNode>left = NULL; newNode>right = NULL; return newNode; } //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list void convertbtToDLL(struct node *node) { //Checks whether node is NULL if(node == NULL) return; //Convert left subtree to doubly linked list convertbtToDLL(node>left); //If list is empty, add node as head of the list if(head == NULL) { //Both head and tail will point to node head = tail = node; } //Otherwise, add node to the end of the list else { //node will be added after tail such that tail's right will point to node tail>right = node; //node's left will point to tail node>left = tail; //node will become new tail tail = node; } //Convert right subtree to doubly linked list convertbtToDLL(node>right); } //display() will print out the nodes of the list void display() { //Node current will point to head struct node *current = head; if(head == NULL) { printf("List is empty\n"); return; } printf("Nodes of generated doubly linked list: \n"); while(current != NULL) { //Prints each node by incrementing pointer. printf("%d ",current>data); current = current>right; } printf("\n"); } int main() { //Add nodes to the binary tree root = createNode(1); root>left = createNode(2); root>right = createNode(3); root>left>left = createNode(4); root>left>right = createNode(5); root>right>left = createNode(6); root>right>right = createNode(7); //Converts the given binary tree to doubly linked list convertbtToDLL(root); //Displays the nodes present in the list display(); return 0; } Output: Nodes of generated doubly linked list: 4 2 5 1 6 3 7 JAVApublic class BinaryTreeToDLL { //Represent a node of the binary tree public static class Node{ int data; Node left; Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; } } //Represent the root of the binary tree public Node root; //Represent the head and tail of the doubly linked list Node head, tail = null; //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list public void convertbtToDLL(Node node) { //Checks whether node is null if(node == null) return; //Convert left subtree to doubly linked list convertbtToDLL(node.left); //If list is empty, add node as head of the list if(head == null) { //Both head and tail will point to node head = tail = node; } //Otherwise, add node to the end of the list else { //node will be added after tail such that tail's right will point to node tail.right = node; //node's left will point to tail node.left = tail; //node will become new tail tail = node; } //Convert right subtree to doubly linked list convertbtToDLL(node.right); } //display() will print out the nodes of the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } System.out.println("Nodes of generated doubly linked list: "); while(current != null) { //Prints each node by incrementing the pointer. System.out.print(current.data + " "); current = current.right; } System.out.println(); } public static void main(String[] args) { BinaryTreeToDLL bt = new BinaryTreeToDLL(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); //Converts the given binary tree to doubly linked list bt.convertbtToDLL(bt.root); //Displays the nodes present in the list bt.display(); } } Output: Nodes of generated doubly linked list: 4 2 5 1 6 3 7 C#using System; namespace DoublyLinkedList { public class Program { //Represent a node of the binary tree public class Node<T>{ public T data; public Node<T> left; public Node<T> right; public Node(T value) { data = value; left = null; right = null; } } public class BinaryTreeToDLL<T>{ //Represent the root of the binary tree public Node<T> root; //Represent the head and tail of the doubly linked list public Node<T> head = null; public Node<T> tail = null; //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list public void convertbtToDLL(Node<T> node) { //Checks whether node is null if(node == null) return; //Convert left subtree to doubly linked list convertbtToDLL(node.left); //If list is empty, add node as head of the list if(head == null) { //Both head and tail will point to node head = tail = node; } //Otherwise, add node to the end of the list else { //node will be added after tail such that tail's right will point to node tail.right = node; //node's left will point to tail node.left = tail; //node will become new tail tail = node; } //Convert right subtree to doubly linked list convertbtToDLL(node.right); } //display() will print out the nodes of the list public void display() { //Node current will point to head Node<T> current = head; if(head == null) { Console.WriteLine("List is empty"); return; } Console.WriteLine("Nodes of generated doubly linked list: "); while(current != null) { //Prints each node by incrementing the pointer. Console.Write(current.data + " "); current = current.right; } Console.WriteLine(); } } public static void Main() { BinaryTreeToDLL<int> bt = new BinaryTreeToDLL<int>(); //Add nodes to the binary tree bt.root = new Node<int>(1); bt.root.left = new Node<int>(2); bt.root.right = new Node<int>(3); bt.root.left.left = new Node<int>(4); bt.root.left.right = new Node<int>(5); bt.root.right.left = new Node<int>(6); bt.root.right.right = new Node<int>(7); //Converts the given binary tree to doubly linked list bt.convertbtToDLL(bt.root); //Displays the nodes present in the list bt.display(); } } } Output: Nodes of generated doubly linked list: 4 2 5 1 6 3 7 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of binary tree class Node{ public $data; public $left; public $right; function __construct($data){ $this>data = $data; $this>left = NULL; $this>right = NULL; } } class BinaryTreeToDLL{ //Represent the root of binary tree public $root; //Represent the head and tail of the doubly linked list public $head; public $tail; function __construct(){ $this>head = NULL; $this>tail = NULL; $this>root = NULL; } //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list function convertbtToDLL($node) { //Checks whether node is null if($node == NULL) return; //Convert left subtree to doubly linked list $this>convertbtToDLL($node>left); //If list is empty, add node as head of the list if($this>head == NULL) { //Both head and tail will point to node $this>head = $this>tail = $node; } //Otherwise, add node to the end of the list else { //node will be added after tail such that tail's right will point to node $this>tail>right = $node; //node's left will point to tail $node>left = $this>tail; //node will become new tail $this>tail = $node; } //Convert right subtree to doubly linked list $this>convertbtToDLL($node>right); } //display() will print out the nodes of the list function display() { //Node current will point to head $current = $this>head; if($this>head == NULL) { print("List is empty <br>"); return; } print("Nodes of generated doubly linked list: <br>"); while($current != NULL) { //Prints each node by incrementing pointer. print($current>data . " "); $current = $current>right; } print("<br>"); } } $bt = new BinaryTreeToDLL(); //Add nodes to the binary tree $bt>root= new Node(1); $bt>root>left = new Node(2); $bt>root>right = new Node(3); $bt>root>left>left = new Node(4); $bt>root>left>right = new Node(5); $bt>root>right>left = new Node(6); $bt>root>right>right = new Node(7); //Converts the given binary tree to doubly linked list $bt>convertbtToDLL($bt>root); //Displays the nodes present in the list $bt>display(); ?> </body> </html> Output: Nodes of generated doubly linked list: 4 2 5 1 6 3 7
Next Topic#
