Convert a given binary tree to Doubly Linked List

Conversion of binary tree to doubly linked list

Here given code implementation process.

/*
  C Program 
  Convert a given binary tree to Doubly Linked List
  //using recursion
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node
{
  int data;
  struct Node*left,*right;
};

//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node* insert(int data)
{
  //create dynamic memory to new binary tree node
  struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
  if(new_node!=NULL)
  {
    //set data and pointer values
    new_node->data=data;
    new_node->left=NULL; //Initially node left-pointer is NULL
    new_node->right=NULL;//Initially node right-pointer is NULL
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
  
}
void  change(struct Node *head, struct Node *leftP, struct Node *rightP) {
  if (head != NULL) {
    change(head->left, leftP, head);
    change(head->right, head, rightP);
    if (head->left == NULL) {
      head->left = leftP;
      if (leftP != NULL) {
        leftP->right = head;
      }
    }
    if (head->right == NULL) {
      head->right = rightP;
      if (rightP != NULL) {
        rightP->left = head;
      }
    }
  }
}
void showDDL(struct Node *root) {
  struct Node *head = root;
  if (head != NULL) {
   
    while (head != NULL) {
      printf("  %d",head->data);
      
      head = head->right;
    }
  }
}
void doublyList(struct Node **root) {
  if (*root != NULL) {
    change(*root, NULL, NULL);
    while ((*root)->left != NULL) {
      *root = (*root)->left;
    }
  }
}

int main()
{

  struct Node*root=NULL;
  /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \    \
        7    9
       / 
      8
  */
  root = insert(1);
  root->left = insert(2);
  root->right = insert(3);
  root->right->right = insert(6);
  root->right->left = insert(5);
  root->right->left->right = insert(9);
  root->left->left = insert(4);
  root->left->left->right = insert(7);
  root->left->left->right->left = insert(8);
  doublyList(&root);
  showDDL(root);
  return 0;
}

Output

4  8  7  2  1  5  9  3  6
/*
  C++ Program
  Convert a given binary tree to Doubly Linked List
  //using recursion
*/
#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinaryTree {
  public:
  Node *root;
  BinaryTree() {
    this->root = NULL;
  }
  void  change(Node *head, Node *leftP, Node *rightP) {
    if (head != NULL) {
      this->change(head->left, leftP, head);
      this->change(head->right, head, rightP);
      if (head->left == NULL) {
        head->left = leftP;
        if (leftP != NULL) {
          leftP->right = head;
        }
      }
      if (head->right == NULL) {
        head->right = rightP;
        if (rightP != NULL) {
          rightP->left = head;
        }
      }
    }
  }
  void showDDL() {
    Node *head = this->root;
    if (head != NULL) {
      cout << ("\n");
      while (head != NULL) {
        cout << "  " << head->data;
        head = head->right;
      }
    }
  }
  void doublyList(Node *head) {
    if (head != NULL) {
      this->change(head, NULL, NULL);
      while (this->root->left != NULL) {
        this->root = this->root->left;
      }
    }
  }
};

int main() {
  BinaryTree obj;
  /*  Make A Binary Tree
  -----------------------
        1
       /  \
      2    3
     /    /  \
    4    5    6
     \    \
      7    9
     / 
    8
  */
  obj.root = new Node(1);
  obj.root->left = new Node(2);
  obj.root->right = new Node(3);
  obj.root->right->right = new Node(6);
  obj.root->right->left = new Node(5);
  obj.root->right->left->right = new Node(9);
  obj.root->left->left = new Node(4);
  obj.root->left->left->right = new Node(7);
  obj.root->left->left->right->left = new Node(8);
  obj.doublyList(obj.root);
  obj.showDDL();
  return 0;
}

Output

4  8  7  2  1  5  9  3  6
/*
  Java Program 
  Convert a given binary tree to Doubly Linked List
  //using recursion
 */

//Structure of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int value) {
    //assign field values
    data = value;
    left = null;
    right = null;
  }
};

public class BinaryTree {

  public Node root;

  public BinaryTree() {
    //set initial tree root to null
    root = null;
  }

  //Function which is convert binary tree to DLL
  public void change(Node head, Node leftP, Node rightP) {
    if (head != null) {
      change(head.left, leftP, head);

      change(head.right, head, rightP);

      if (head.left == null) {
        head.left = leftP;

        if (leftP != null) {
          leftP.right = head;
        }

      }
      if (head.right == null) {
        head.right = rightP;
        if (rightP != null) {
          rightP.left = head;
        }
      }
    }
  }
  //Display data in doubly linked list
  public void showDDL() {
    Node head = root;
    if (head != null) {
      System.out.println();

      while (head != null) {

        System.out.print("  " + head.data);
        head = head.right;
      }
    }
  }
  public void doublyList(Node head) {
    if (head != null) {
      //Covert into Doubly linked list
      change(head, null, null);

      //reset root to first inorder node
      while (root.left != null) {
        //Set root node
        root = root.left;
      }

    }
  }
  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /*  Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \    \
          7    9
         / 
        8
    */
    //Add binary tree elements
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(6);
    obj.root.right.left = new Node(5);
    obj.root.right.left.right = new Node(9);
    obj.root.left.left = new Node(4);
    obj.root.left.left.right = new Node(7);

    obj.root.left.left.right.left = new Node(8);

    obj.doublyList(obj.root);

    obj.showDDL();

  }
}

Output

4  8  7  2  1  5  9  3  6
/*
  C# Program 
  Convert a given binary tree to Doubly Linked List
  //using recursion
 */
using System;
//Structure of Binary Tree node
public class Node {

	public int data;
	public Node left, right;
	//make a tree node
	public Node(int value) {
		//assign field values
		data = value;
		left = null;
		right = null;
	}
};

public class BinaryTree {

	public Node root;

	public BinaryTree() {
		//set initial tree root to null
		root = null;
	}

	//Function which is convert binary tree to DLL
	public void change(Node head, Node leftP, Node rightP) {
		if (head != null) {
			change(head.left, leftP, head);

			change(head.right, head, rightP);

			if (head.left == null) {
				head.left = leftP;

				if (leftP != null) {
					leftP.right = head;
				}

			}
			if (head.right == null) {
				head.right = rightP;
				if (rightP != null) {
					rightP.left = head;
				}
			}
		}
	}
	//Display data in doubly linked list
	public void showDDL() {
		Node head = root;
		if (head != null) {
			Console.WriteLine();

			while (head != null) {

				Console.Write("  " + head.data);
				head = head.right;
			}
		}
	}
	public void doublyList(Node head) {
		if (head != null) {
			//Covert into Doubly linked list
			change(head, null, null);

			//reset root to first inorder node
			while (root.left != null) {
				//Set root node
				root = root.left;
			}

		}
	}
	public static void Main(String[] args) {
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();

		/*  Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \    \
          7    9
         / 
        8
    */
		//Add binary tree elements
		obj.root = new Node(1);
		obj.root.left = new Node(2);
		obj.root.right = new Node(3);
		obj.root.right.right = new Node(6);
		obj.root.right.left = new Node(5);
		obj.root.right.left.right = new Node(9);
		obj.root.left.left = new Node(4);
		obj.root.left.left.right = new Node(7);

		obj.root.left.left.right.left = new Node(8);

		obj.doublyList(obj.root);

		obj.showDDL();

	}
}

Output

4  8  7  2  1  5  9  3  6
# Python Program 
# Convert a given binary tree to Doubly Linked List
class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinaryTree :

  def __init__(self) :
    self.root = None
  
  def change(self, head, leftP, rightP) :
    if (head != None) :
      self.change(head.left, leftP, head)
      self.change(head.right, head, rightP)
      if (head.left == None) :
        head.left = leftP
        if (leftP != None) :
          leftP.right = head
        
      
      if (head.right == None) :
        head.right = rightP
        if (rightP != None) :
          rightP.left = head
        
      
    
  
  def showDDL(self) :
    head = self.root
    if (head != None) :
      print()
      while (head != None) :
        print(head.data,end="  ")
        head = head.right
      
    
  
  def doublyList(self, head) :
    if (head != None) :
      self.change(head, None, None)
      while (self.root.left != None) :
        self.root = self.root.left
      
    
  
def main() :
  obj = BinaryTree()
  #  Make A Binary Tree
  #          1
  #         /  \
  #        2    3
  #       /    /  \
  #      4    5    6
  #       \    \
  #        7    9
  #       /
  #      8
  #  
  obj.root = Node(1)
  obj.root.left = Node(2)
  obj.root.right = Node(3)
  obj.root.right.right = Node(6)
  obj.root.right.left = Node(5)
  obj.root.right.left.right = Node(9)
  obj.root.left.left = Node(4)
  obj.root.left.left.right = Node(7)
  obj.root.left.left.right.left = Node(8)
  obj.doublyList(obj.root)
  obj.showDDL()
  

if __name__ == "__main__":
  main()

Output

4  8  7  2  1  5  9  3  6
# Ruby Program
# Convert a given binary tree to Doubly Linked List
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinaryTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def change(head, leftP, rightP) 
		if (head != nil) 
			self.change(head.left, leftP, head)
			self.change(head.right, head, rightP)
			if (head.left == nil) 
				head.left = leftP
				if (leftP != nil) 
					leftP.right = head
				end
			end
			if (head.right == nil) 
				head.right = rightP
				if (rightP != nil) 
					rightP.left = head
				end
			end
		end
	end
	def showDDL() 
		head = @root
		if (head != nil) 
			print("\n")
			while (head != nil) 
				print("  ", head.data)
				head = head.right
			end
		end
	end
	def doublyList(head) 
		if (head != nil) 
			self.change(head, nil, nil)
			while (@root.left != nil) 
				@root = @root.left
			end
		end
	end
end

def main() 
	obj = BinaryTree.new()
	#  Make A Binary Tree
	#          1
	#         /  \
	#        2    3
	#       /    /  \
	#      4    5    6
	#       \    \
	#        7    9
	#       /
	#      8
	#  
	obj.root = Node.new(1)
	obj.root.left = Node.new(2)
	obj.root.right = Node.new(3)
	obj.root.right.right = Node.new(6)
	obj.root.right.left = Node.new(5)
	obj.root.right.left.right = Node.new(9)
	obj.root.left.left = Node.new(4)
	obj.root.left.left.right = Node.new(7)
	obj.root.left.left.right.left = Node.new(8)
	obj.doublyList(obj.root)
	obj.showDDL()
end

main()

Output

4  8  7  2  1  5  9  3  6
<?php
/*
  Php Program
  Convert a given binary tree to Doubly Linked List
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinaryTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function change($head, $leftP, $rightP) {
    if ($head != null) {
      $this->change($head->left, $leftP, $head);
      $this->change($head->right, $head, $rightP);
      if ($head->left == null) {
        $head->left = $leftP;
        if ($leftP != null) {
          $leftP->right = $head;
        }
      }
      if ($head->right == null) {
        $head->right = $rightP;
        if ($rightP != null) {
          $rightP->left = $head;
        }
      }
    }
  }
  public  function showDDL() {
    $head = $this->root;
    if ($head != null) {
      echo("\n");
      while ($head != null) {
        echo("  ".$head->data);
        $head = $head->right;
      }
    }
  }
  public  function doublyList($head) {
    if ($head != null) {
      $this->change($head, null, null);
      while ($this->root->left != null) {
        $this->root = $this->root->left;
      }
    }
  }
}

function main() {
  $obj = new BinaryTree();
  $obj->root = new Node(1);
  $obj->root->left = new Node(2);
  $obj->root->right = new Node(3);
  $obj->root->right->right = new Node(6);
  $obj->root->right->left = new Node(5);
  $obj->root->right->left->right = new Node(9);
  $obj->root->left->left = new Node(4);
  $obj->root->left->left->right = new Node(7);
  $obj->root->left->left->right->left = new Node(8);
  $obj->doublyList($obj->root);
  $obj->showDDL();
}
main();

Output

4  8  7  2  1  5  9  3  6
/*
  Node JS Program
  Convert a given binary tree to Doubly Linked List
*/
class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
};
class BinaryTree {
	
	constructor() {
		this.root = null;
	}
	change(head, leftP, rightP) {
		if (head != null) {
			this.change(head.left, leftP, head);
			this.change(head.right, head, rightP);
			if (head.left == null) {
				head.left = leftP;
				if (leftP != null) {
					leftP.right = head;
				}
			}
			if (head.right == null) {
				head.right = rightP;
				if (rightP != null) {
					rightP.left = head;
				}
			}
		}
	}
	showDDL() {
		var head = this.root;
		if (head != null) {
			process.stdout.write();
			while (head != null) {
				process.stdout.write("  " + head.data);
				head = head.right;
			}
		}
	}
	doublyList(head) {
		if (head != null) {
			this.change(head, null, null);
			while (this.root.left != null) {
				this.root = this.root.left;
			}
		}
	}
}
function main() {
	var obj = new BinaryTree();
	/*  Make A Binary Tree
    -----------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \    \
          7    9
         / 
        8
    */
	obj.root = new Node(1);
	obj.root.left = new Node(2);
	obj.root.right = new Node(3);
	obj.root.right.right = new Node(6);
	obj.root.right.left = new Node(5);
	obj.root.right.left.right = new Node(9);
	obj.root.left.left = new Node(4);
	obj.root.left.left.right = new Node(7);
	obj.root.left.left.right.left = new Node(8);
	obj.doublyList(obj.root);
	obj.showDDL();
}
main();

Output

4  8  7  2  1  5  9  3  6
/*
  Swift 4 Program
  Convert a given binary tree to Doubly Linked List
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
};
class BinaryTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func change(_ head: Node? , _ leftP : Node? , _ rightP : Node? ) {
    if (head != nil) {
      self.change(head!.left, leftP, head);
      self.change(head!.right, head, rightP);
      if (head!.left == nil) {
        head!.left = leftP;
        if (leftP != nil) {
          leftP!.right = head;
        }
      }
      if (head!.right == nil) {
        head!.right = rightP;
        if (rightP != nil) {
          rightP!.left = head;
        }
      }
    }
  }
  func showDDL() {
    var head: Node? = self.root;
    if (head != nil) {
     
      while (head != nil) {
        print(head!.data, terminator : "  ");
        head = head!.right;
      }
    }
  }
  func doublyList(_ head: Node? ) {
    if (head != nil) {
      self.change(head, nil, nil);
      while (self.root!.left != nil) {
        self.root = self.root!.left;
      }
    }
  }

}
func main() {
  let obj: BinaryTree = BinaryTree();
  /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \    \
        7    9
       / 
      8
  */
  obj.root = Node(1);
  obj.root!.left = Node(2);
  obj.root!.right = Node(3);
  obj.root!.right!.right = Node(6);
  obj.root!.right!.left = Node(5);
  obj.root!.right!.left!.right = Node(9);
  obj.root!.left!.left = Node(4);
  obj.root!.left!.left!.right = Node(7);
  obj.root!.left!.left!.right!.left = Node(8);
  obj.doublyList(obj.root);
  obj.showDDL();
}
main();

Output

4  8  7  2  1  5  9  3  6

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







© 2021, kalkicode.com, All rights reserved