Extract leaves of a binary tree in a doubly linked list

Here given code implementation process.

/*
  C Program  
  Extract leaves of a binary tree in a doubly linked list
*/
#include <stdio.h>

#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
	// Create dynamic 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;
		new_node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return new_node;
}
//Recursive function
//Display preorder view of binary tree
void pre_order(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		pre_order(node->left);
		pre_order(node->right);
	}
}
//Extract leaf nodes in given binary tree and added into doubly linked list
struct Node *extract_leaves(struct Node *node, struct Node **front)
{
	if (node != NULL)
	{
		if (node->left == NULL && node->right == NULL)
		{
			//Add node at front of linked list
			node->right = *front;
			if ( *front != NULL)
			{
				// When this is not first node
				// Combine left direction
				( *front)->left = node;
			}*front = node;
			//Returns null value to the previous node child
			return NULL;
		}
		node->right = extract_leaves(node->right, front);
		node->left = extract_leaves(node->left, front);
		return node;
	}
}
//Handling the request of extract the leaf node in binary tree
struct Node *get_leaves(struct Node **root)
{
	struct Node *front = NULL;*root = extract_leaves( *root, &front);
	return front;
}
//Display flatten elements of tree
void show_doubly_list(struct Node *front)
{
	if (front == NULL)
	{
		printf("\n Doubly Linked list is empty\n");
		return;
	}
	printf("\n Doubly Linked list : \n");
	struct Node *temp = front;
	//Iterate Linked list elements
	while (temp != NULL)
	{
		printf("  %d", temp->data);
		//visit to next node
		temp = temp->right;
	}
	printf("\n");
}
int main()
{
	//Define tree root
	struct Node *root = NULL;
	//Linked list 
	struct Node *front = NULL;
	/*
    Construct Binary Tree
    -----------------------
          10
         /   \
        6     8
       / \   / \
      2   3 7   5
     /       \   \
    9        -6   13

   
    */
	//Add nodes
	root = get_node(10);
	root->left = get_node(6);
	root->left->left = get_node(2);
	root->right = get_node(8);
	root->right->right = get_node(5);
	root->right->left = get_node(7);
	root->right->left->right = get_node(-6);
	root->left->right = get_node(3);
	root->left->left->left = get_node(9);
	root->right->right->right = get_node(13);
	//Display tree elements
	printf("\n Preorder : \n");
	pre_order(root);
	front = get_leaves( &root);
	printf("\n After Extract Leaf Node");
	printf("\n Preorder : \n");
	pre_order(root);
	show_doubly_list(front);
	return 0;
}

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
/* 
  Java Program 
  Extract leaves of a binary tree in a doubly linked list
*/

//Node of Binary Tree
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public Node root;
	public Node front;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		//This is initial linked list node
		this.front = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void pre_order(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Display extract leaves in tree
	public void show_doubly_list()
	{
		if (this.front == null)
		{
			System.out.print("\n Empty Linked List \n");
			return;
		}
		System.out.print("\n Doubly Linked list : \n");
		//Start to front node
		Node temp = this.front;
		//Iterate Linked list elements
		while (temp != null)
		{
			//Display node value
			System.out.print("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
		System.out.print("\n");
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	public Node extract_leaves(Node node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				//Add node at front of linked list
				node.right = this.front;
				if (this.front != null)
				{
					// When this is not first node
					// Combine left direction
					this.front.left = node;
				}
				this.front = node;
				//Returns null value to the previous node child
				return null;
			}
			node.right = extract_leaves(node.right);
			node.left = extract_leaves(node.left);
			return node;
		}
		return null;
	}
	public static void main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/* 
        Construct Binary Tree
        -----------------------
              10
             /   \
            6     8
           / \   / \
          2   3 7   5
         /       \   \
        9        -6   13

       
        */
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(5);
		obj.root.right.left = new Node(7);
		obj.root.right.left.right = new Node(-6);
		obj.root.left.right = new Node(3);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(13);
		//Display tree elements
		System.out.print("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.extract_leaves(obj.root);
		//After transform
		System.out.print("\n After Extract Leaf Node");
		System.out.print("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.show_doubly_list();
	}
}

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
//Include header file
#include <iostream>
using namespace std;
/*
  C++ Program 
  Extract leaves of a binary tree in a doubly linked list
*/

//Node of Binary Tree
class Node
{
	public: 
    int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    Node *root;
	Node *front;
	BinaryTree()
	{
		//Set initial tree root to null
		this->root = NULL;
		//This is initial linked list node
		this->front = NULL;
	}
	//Recursive function
	//Display preorder view of binary tree
	void pre_order(Node *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << "  " << node->data;
			this->pre_order(node->left);
			this->pre_order(node->right);
		}
	}
	//Display extract leaves in tree
	void show_doubly_list()
	{
		if (this->front == NULL)
		{
			cout << "\n Empty Linked List \n";
			return;
		}
		cout << "\n Doubly Linked list : \n";
		//Start to front node
		Node *temp = this->front;
		//Iterate Linked list elements
		while (temp != NULL)
		{
			//Display node value
			cout << "  " << temp->data;
			//visit to next node
			temp = temp->right;
		}
		cout << "\n";
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	Node *extract_leaves(Node *node)
	{
		if (node != NULL)
		{
			if (node->left == NULL && node->right == NULL)
			{
				//Add node at front of linked list
				node->right = this->front;
				if (this->front != NULL)
				{
					// When this is not first node
					// Combine left direction
					this->front->left = node;
				}
				this->front = node;
				//Returns null value to the previous node child
				return NULL;
			}
			node->right = this->extract_leaves(node->right);
			node->left = this->extract_leaves(node->left);
			return node;
		}
		return NULL;
	}
};
int main()
{
	//Make object of Binary Tree
	BinaryTree obj = BinaryTree();
	/*
	        Construct Binary Tree
	        -----------------------
	              10
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /       \   \
	        9        -6   13

	       
	        */
	//Add nodes
	obj.root = new Node(10);
	obj.root->left = new Node(6);
	obj.root->left->left = new Node(2);
	obj.root->right = new Node(8);
	obj.root->right->right = new Node(5);
	obj.root->right->left = new Node(7);
	obj.root->right->left->right = new Node(-6);
	obj.root->left->right = new Node(3);
	obj.root->left->left->left = new Node(9);
	obj.root->right->right->right = new Node(13);
	//Display tree elements
	cout << "\n Preorder : \n";
	obj.pre_order(obj.root);
	obj.extract_leaves(obj.root);
	//After transform
	cout << "\n After Extract Leaf Node";
	cout << "\n Preorder : \n";
	obj.pre_order(obj.root);
	obj.show_doubly_list();
	return 0;
}

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
//Include namespace system
using System;
/* 
  C# Program 
  Extract leaves of a binary tree in a doubly linked list
*/
//Node of Binary Tree
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public Node root;
	public Node front;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		//This is initial linked list node
		this.front = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void pre_order(Node node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write("  " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Display extract leaves in tree
	public void show_doubly_list()
	{
		if (this.front == null)
		{
			Console.Write("\n Empty Linked List \n");
			return;
		}
		Console.Write("\n Doubly Linked list : \n");
		//Start to front node
		Node temp = this.front;
		//Iterate Linked list elements
		while (temp != null)
		{
			//Display node value
			Console.Write("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
		Console.Write("\n");
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	public Node extract_leaves(Node node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				//Add node at front of linked list
				node.right = this.front;
				if (this.front != null)
				{
					// When this is not first node
					// Combine left direction
					this.front.left = node;
				}
				this.front = node;
				//Returns null value to the previous node child
				return null;
			}
			node.right = extract_leaves(node.right);
			node.left = extract_leaves(node.left);
			return node;
		}
		return null;
	}
	public static void Main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/* 
		        Construct Binary Tree
		        -----------------------
		              10
		             /   \
		            6     8
		           / \   / \
		          2   3 7   5
		         /       \   \
		        9        -6   13

		       
		        */
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(5);
		obj.root.right.left = new Node(7);
		obj.root.right.left.right = new Node(-6);
		obj.root.left.right = new Node(3);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(13);
		//Display tree elements
		Console.Write("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.extract_leaves(obj.root);
		//After transform
		Console.Write("\n After Extract Leaf Node");
		Console.Write("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.show_doubly_list();
	}
}

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
<?php
/* 
  Php Program 
  Extract leaves of a binary tree in a doubly linked list
*/
//Node of Binary Tree
class Node
{
	public $data;
	public $left;
	public $right;

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

	function __construct()
	{
		//Set initial tree root to null
		$this->root = null;
		//This is initial linked list node
		$this->front = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public	function pre_order($node)
	{
		if ($node != null)
		{
			//Print node value
			echo "  ". $node->data;
			$this->pre_order($node->left);
			$this->pre_order($node->right);
		}
	}
	//Display extract leaves in tree
	public	function show_doubly_list()
	{
		if ($this->front == null)
		{
			echo "\n Empty Linked List \n";
			return;
		}
		echo "\n Doubly Linked list : \n";
		//Start to front node
		$temp = $this->front;
		//Iterate Linked list elements
		while ($temp != null)
		{
			//Display node value
			echo "  ". $temp->data;
			//visit to next node
			$temp = $temp->right;
		}
		echo "\n";
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	public	function extract_leaves($node)
	{
		if ($node != null)
		{
			if ($node->left == null && $node->right == null)
			{
				//Add node at front of linked list
				$node->right = $this->front;
				if ($this->front != null)
				{
					// When this is not first node
					// Combine left direction
					$this->front->left = $node;
				}
				$this->front = $node;
				//Returns null value to the previous node child
				return null;
			}
			$node->right = $this->extract_leaves($node->right);
			$node->left = $this->extract_leaves($node->left);
			return $node;
		}
		return null;
	}
}

function main()
{
	//Make object of Binary Tree
	$obj = new BinaryTree();
	/* 
	        Construct Binary Tree
	        -----------------------
	              10
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /       \   \
	        9        -6   13

	       
	        */
	//Add nodes
	$obj->root = new Node(10);
	$obj->root->left = new Node(6);
	$obj->root->left->left = new Node(2);
	$obj->root->right = new Node(8);
	$obj->root->right->right = new Node(5);
	$obj->root->right->left = new Node(7);
	$obj->root->right->left->right = new Node(-6);
	$obj->root->left->right = new Node(3);
	$obj->root->left->left->left = new Node(9);
	$obj->root->right->right->right = new Node(13);
	//Display tree elements
	echo "\n Preorder : \n";
	$obj->pre_order($obj->root);
	$obj->extract_leaves($obj->root);
	//After transform
	echo "\n After Extract Leaf Node";
	echo "\n Preorder : \n";
	$obj->pre_order($obj->root);
	$obj->show_doubly_list();
}
main();

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
/* 
  Node Js Program 
  Extract leaves of a binary tree in a doubly linked list
*/
//Node of Binary Tree
class Node
{
	constructor(data)
	{
		//Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		//Set initial tree root to null
		this.root = null;
		//This is initial linked list node
		this.front = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	pre_order(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write("  " + node.data);
			this.pre_order(node.left);
			this.pre_order(node.right);
		}
	}
	//Display extract leaves in tree
	show_doubly_list()
	{
		if (this.front == null)
		{
			process.stdout.write("\n Empty Linked List \n");
			return;
		}
		process.stdout.write("\n Doubly Linked list : \n");
		//Start to front node
		var temp = this.front;
		//Iterate Linked list elements
		while (temp != null)
		{
			//Display node value
			process.stdout.write("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
		process.stdout.write("\n");
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	extract_leaves(node)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				//Add node at front of linked list
				node.right = this.front;
				if (this.front != null)
				{
					// When this is not first node
					// Combine left direction
					this.front.left = node;
				}
				this.front = node;
				//Returns null value to the previous node child
				return null;
			}
			node.right = this.extract_leaves(node.right);
			node.left = this.extract_leaves(node.left);
			return node;
		}
		return null;
	}
}

function main()
{
	//Make object of Binary Tree
	var obj = new BinaryTree();
	/* 
	        Construct Binary Tree
	        -----------------------
	              10
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /       \   \
	        9        -6   13

	       
	        */
	//Add nodes
	obj.root = new Node(10);
	obj.root.left = new Node(6);
	obj.root.left.left = new Node(2);
	obj.root.right = new Node(8);
	obj.root.right.right = new Node(5);
	obj.root.right.left = new Node(7);
	obj.root.right.left.right = new Node(-6);
	obj.root.left.right = new Node(3);
	obj.root.left.left.left = new Node(9);
	obj.root.right.right.right = new Node(13);
	//Display tree elements
	process.stdout.write("\n Preorder : \n");
	obj.pre_order(obj.root);
	obj.extract_leaves(obj.root);
	//After transform
	process.stdout.write("\n After Extract Leaf Node");
	process.stdout.write("\n Preorder : \n");
	obj.pre_order(obj.root);
	obj.show_doubly_list();
}
main();

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
#   Python 3 Program 
#   Extract leaves of a binary tree in a doubly linked list

# Node of Binary Tree
class Node :
	
	def __init__(self, data) :
		# Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	
	def __init__(self) :
		# Set initial tree root to null
		self.root = None
		# This is initial linked list node
		self.front = None
	
	# Recursive function
	# Display preorder view of binary tree
	def pre_order(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.pre_order(node.left)
			self.pre_order(node.right)
		
	
	# Display extract leaves in tree
	def show_doubly_list(self) :
		if (self.front == None) :
			print("\n Empty Linked List \n", end = "")
			return
		
		print("\n Doubly Linked list : \n", end = "")
		# Start to front node
		temp = self.front
		# Iterate Linked list elements
		while (temp != None) :
			# Display node value
			print("  ", temp.data, end = "")
			# visit to next node
			temp = temp.right
		
		print("\n", end = "")
	
	# Extract leaf nodes in given binary tree and added into doubly linked list
	def extract_leaves(self, node) :
		if (node != None) :
			if (node.left == None and node.right == None) :
				# Add node at front of linked list
				node.right = self.front
				if (self.front != None) :
					#  When this is not first node
					#  Combine left direction
					self.front.left = node
				
				self.front = node
				# Returns null value to the previous node child
				return None
			
			node.right = self.extract_leaves(node.right)
			node.left = self.extract_leaves(node.left)
			return node
		
		return None
	

def main() :
	# Make object of Binary Tree
	obj = BinaryTree()
	#  
	#         Construct Binary Tree
	#         -----------------------
	#               10
	#              /   \
	#             6     8
	#            / \   / \
	#           2   3 7   5
	#          /       \   \
	#         9        -6   13
	#        
	#         
	
	# Add nodes
	obj.root = Node(10)
	obj.root.left = Node(6)
	obj.root.left.left = Node(2)
	obj.root.right = Node(8)
	obj.root.right.right = Node(5)
	obj.root.right.left = Node(7)
	obj.root.right.left.right = Node(-6)
	obj.root.left.right = Node(3)
	obj.root.left.left.left = Node(9)
	obj.root.right.right.right = Node(13)
	# Display tree elements
	print("\n Preorder : \n", end = "")
	obj.pre_order(obj.root)
	obj.extract_leaves(obj.root)
	# After transform
	print("\n After Extract Leaf Node", end = "")
	print("\n Preorder : \n", end = "")
	obj.pre_order(obj.root)
	obj.show_doubly_list()

if __name__ == "__main__": main()

Output

 Preorder :
   10   6   2   9   3   8   7   -6   5   13
 After Extract Leaf Node
 Preorder :
   10   6   2   8   7   5
 Doubly Linked list :
   9   3   -6   13
#   Ruby Program 
#   Extract leaves of a binary tree in a doubly linked list

# Node of Binary Tree
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		# Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end
end
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root, :front
	attr_accessor :root, :front
 
	
	def initialize() 
		# Set initial tree root to null
		self.root = nil
		# This is initial linked list node
		self.front = nil
	end
	# Recursive function
	# Display preorder view of binary tree
	def pre_order(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.pre_order(node.left)
			self.pre_order(node.right)
		end
	end
	# Display extract leaves in tree
	def show_doubly_list() 
		if (self.front == nil) 
			print("\n Empty Linked List \n")
			return
		end
		print("\n Doubly Linked list : \n")
		# Start to front node
		temp = self.front
		# Iterate Linked list elements
		while (temp != nil) 
			# Display node value
			print("  ", temp.data)
			# visit to next node
			temp = temp.right
		end
		print("\n")
	end
	# Extract leaf nodes in given binary tree and added into doubly linked list
	def extract_leaves(node) 
		if (node != nil) 
			if (node.left == nil && node.right == nil) 
				# Add node at front of linked list
				node.right = self.front
				if (self.front != nil) 
					#  When this is not first node
					#  Combine left direction
					self.front.left = node
				end
				self.front = node
				# Returns null value to the previous node child
				return nil
			end
			node.right = self.extract_leaves(node.right)
			node.left = self.extract_leaves(node.left)
			return node
		end
		return nil
	end
end
def main() 
	# Make object of Binary Tree
	obj = BinaryTree.new()
	#  
	#         Construct Binary Tree
	#         -----------------------
	#               10
	#              /   \
	#             6     8
	#            / \   / \
	#           2   3 7   5
	#          /       \   \
	#         9        -6   13
	#        
	#         
	
	# Add nodes
	obj.root = Node.new(10)
	obj.root.left = Node.new(6)
	obj.root.left.left = Node.new(2)
	obj.root.right = Node.new(8)
	obj.root.right.right = Node.new(5)
	obj.root.right.left = Node.new(7)
	obj.root.right.left.right = Node.new(-6)
	obj.root.left.right = Node.new(3)
	obj.root.left.left.left = Node.new(9)
	obj.root.right.right.right = Node.new(13)
	# Display tree elements
	print("\n Preorder : \n")
	obj.pre_order(obj.root)
	obj.extract_leaves(obj.root)
	# After transform
	print("\n After Extract Leaf Node")
	print("\n Preorder : \n")
	obj.pre_order(obj.root)
	obj.show_doubly_list()
end
main()

Output

 Preorder : 
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder : 
  10  6  2  8  7  5
 Doubly Linked list : 
  9  3  -6  13
/* 
  Scala Program 
  Extract leaves of a binary tree in a doubly linked list
*/
//Node of Binary Tree
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: Node,
	var front: Node)
{
	def this()
	{
		this(null, null);
	}
	//Recursive function
	//Display preorder view of binary tree
	def pre_order(node: Node): Unit = {
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Display extract leaves in tree
	def show_doubly_list(): Unit = {
		if (this.front == null)
		{
			print("\n Empty Linked List \n");
			return;
		}
		print("\n Doubly Linked list : \n");
		//Start to front node
		var temp: Node = this.front;
		//Iterate Linked list elements
		while (temp != null)
		{
			//Display node value
			print("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
		print("\n");
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	def extract_leaves(node: Node): Node = {
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				//Add node at front of linked list
				node.right = this.front;
				if (this.front != null)
				{
					// When this is not first node
					// Combine left direction
					this.front.left = node;
				}
				this.front = node;
				//Returns null value to the previous node child
				return null;
			}
			node.right = extract_leaves(node.right);
			node.left = extract_leaves(node.left);
			return node;
		}
		return null;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of Binary Tree
		var obj: BinaryTree = new BinaryTree();
		/* 
		        Construct Binary Tree
		        -----------------------
		              10
		             /   \
		            6     8
		           / \   / \
		          2   3 7   5
		         /       \   \
		        9        -6   13

		       
		        */
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(5);
		obj.root.right.left = new Node(7);
		obj.root.right.left.right = new Node(-6);
		obj.root.left.right = new Node(3);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(13);
		//Display tree elements
		print("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.extract_leaves(obj.root);
		//After transform
		print("\n After Extract Leaf Node");
		print("\n Preorder : \n");
		obj.pre_order(obj.root);
		obj.show_doubly_list();
	}
}

Output

 Preorder :
  10  6  2  9  3  8  7  -6  5  13
 After Extract Leaf Node
 Preorder :
  10  6  2  8  7  5
 Doubly Linked list :
  9  3  -6  13
/* 
  Swift 4 Program 
  Extract leaves of a binary tree in a doubly linked list
*/
//Node of Binary Tree
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: Node? ;
	var front: Node? ;
	init()
	{
		//Set initial tree root to null
		self.root = nil;
		//This is initial linked list node
		self.front = nil;
	}
	//Recursive function
	//Display preorder view of binary tree
	func pre_order(_ node: Node? )
	{
		if (node != nil)
		{
			//Print node value
			print("  ", node!.data, terminator: "");
			self.pre_order(node!.left);
			self.pre_order(node!.right);
		}
	}
	//Display extract leaves in tree
	func show_doubly_list()
	{
		if (self.front == nil)
		{
			print("\n Empty Linked List \n", terminator: "");
			return;
		}
		print("\n Doubly Linked list : \n", terminator: "");
		//Start to front node
		var temp: Node? = self.front;
		//Iterate Linked list elements
		while (temp != nil)
		{
			//Display node value
			print("  ", temp!.data, terminator: "");
			//visit to next node
			temp = temp!.right;
		}
		print("\n", terminator: "");
	}
	//Extract leaf nodes in given binary tree and added into doubly linked list
	func extract_leaves(_ node: Node? ) -> Node?
	{
		if (node != nil)
		{
			if (node!.left == nil && node!.right == nil)
			{
				//Add node at front of linked list
				node!.right = self.front;
				if (self.front != nil)
				{
					// When this is not first node
					// Combine left direction
					self.front!.left = node;
				}
				self.front = node;
				//Returns null value to the previous node child
				return nil;
			}
			node!.right = self.extract_leaves(node!.right);
			node!.left = self.extract_leaves(node!.left);
			return node;
		}
		return nil;
	}
}
func main()
{
	//Make object of Binary Tree
	let obj: BinaryTree = BinaryTree();
	/* 
	        Construct Binary Tree
	        -----------------------
	              10
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /       \   \
	        9        -6   13

	       
	 */
	//Add nodes
	obj.root = Node(10);
	obj.root!.left = Node(6);
	obj.root!.left!.left = Node(2);
	obj.root!.right = Node(8);
	obj.root!.right!.right = Node(5);
	obj.root!.right!.left = Node(7);
	obj.root!.right!.left!.right = Node(-6);
	obj.root!.left!.right = Node(3);
	obj.root!.left!.left!.left = Node(9);
	obj.root!.right!.right!.right = Node(13);
	//Display tree elements
	print("\n Preorder : \n", terminator: "");
	obj.pre_order(obj.root);
	let _ = obj.extract_leaves(obj.root);
	//After transform
	print("\n After Extract Leaf Node", terminator: "");
	print("\n Preorder : \n", terminator: "");
	obj.pre_order(obj.root);
	obj.show_doubly_list();
}
main();

Output

 Preorder :
   10   6   2   9   3   8   7   -6   5   13
 After Extract Leaf Node
 Preorder :
   10   6   2   8   7   5
 Doubly Linked list :
   9   3   -6   13

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