Skip to main content

Flatten a binary tree into linked list

Here given code implementation process.

/*
  C Program  
  Flatten a binary tree into 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 preorder(struct Node *node)
{
	if (node)
	{
		//Print node value
		printf("  %d", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
//This are flattening tree nodes in inorder from
void flatten_nodes(struct Node *node, struct Node **back)
{
	if (node == NULL)
	{
		return;
	}
	//Get right subtree of node
	struct Node *right_side = node->right;
	if ( *back == NULL)
	{
		//When first node of tree
		*back = node;
	}
	else
	{
		//connect previous node to current node
		(*back)->right = node;
		(*back)->left = NULL;
        *back = node;
	}
	flatten_nodes(node->left, back);
	flatten_nodes(right_side, back);
}
//This are handling the request of flatten tree nodes in pre order from
void transform(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	struct Node *back = NULL;
	flatten_nodes(root, &back);
	if (back != NULL)
	{
		//Set last node of pre order
		back->left = NULL;
		back->right = NULL;
	}
}
//Display flatten elements of tree
void show_element(struct Node *root)
{
	if (root == NULL)
	{
		printf("\n Empty Tree\n");
		return;
	}
	printf("\n Flatten Tree Node is :");
	struct Node *temp = root;
	while (temp != NULL)
	{
		printf("  %d", temp->data);
		//visit to next node
		temp = temp->right;
	}
}
int main()
{
	struct Node *root = NULL;
	/*
    Construct Binary Tree
    -----------------------
           1
         /   \
        6     8
       / \   / \
      2   3 7   5
     /   /   \   \
    9   4    -6   11

   
    */
	//Add nodes
	root = get_node(1);
	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->right->left = get_node(4);
	root->left->left->left = get_node(9);
	root->right->right->right = get_node(11);
	//Display tree elements
	printf("\n Preorder Tree Nodes : ");
	preorder(root);
	printf("\n");
	transform(root);
	//After transform
	show_element(root);
	return 0;
}

Output

 Preorder Tree Nodes :   1  6  2  9  3  4  8  7  -6  5  11

 Flatten Tree Node is :  1  6  2  9  3  4  8  7  -6  5  11
/* 
  Java Program 
  Flatten a binary tree into 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 back;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		this.back = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//This are flattening tree nodes in preorder from
	public void flatten_nodes(Node node)
	{
		if (node != null)
		{
			//Get right subtree of node
			Node right_side = node.right;
			if (this.back == null)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				this.back = node;
			}
			else
			{
				this.back.right = node;
				this.back.left = null;
				this.back = node;
			}
			//recursive executing left and right subtree
			flatten_nodes(node.left);
			flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	public void transform()
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		this.back = null;
		//Perform flatten operation
		flatten_nodes(this.root);
		if (this.back != null)
		{
			// Set last node of perorde
			this.back.left = null;
			this.back.right = null;
		}
		this.back = null;
	}
	//Display flatten elements of tree
	public void show_element()
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Tree\n");
			return;
		}
		System.out.print("\n Flatten Tree Node in preorder : \n");
		Node temp = this.root;
		//Iterate tree elements
		while (temp != null)
		{
			//Display node value
			System.out.print("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
	}
	public static void main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/* 
        Construct Binary Tree
        -----------------------
               1
             /   \
            6     8
           / \   / \
          2   3 7   5
         /   /   \   \
        9   4    -6   11

       
        */
		//Add nodes
		obj.root = new Node(1);
		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.right.left = new Node(4);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(11);
		//Display tree elements
		System.out.print("\n Preorder Tree Nodes  : \n");
		obj.preorder(obj.root);
		//Perform transformation
		obj.transform();
		//After transform
		obj.show_element();;
	}
}

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
//Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Flatten a binary tree into 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 *back;
	BinaryTree()
	{
		//Set initial tree root to null
		this->root = NULL;
		this->back = NULL;
	}
	//Recursive function
	//Display preorder view of binary tree
	void preorder(Node *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << "  " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
	//This are flattening tree nodes in preorder from
	void flatten_nodes(Node *node)
	{
		if (node != NULL)
		{
			//Get right subtree of node
			Node *right_side = node->right;
			if (this->back == NULL)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				this->back = node;
			}
			else
			{
				this->back->right = node;
				this->back->left = NULL;
				this->back = node;
			}
			//recursive executing left and right subtree
			this->flatten_nodes(node->left);
			this->flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	void transform()
	{
		if (this->root == NULL)
		{
			// When empty tree
			return;
		}
		// Set back node
		this->back = NULL;
		//Perform flatten operation
		this->flatten_nodes(this->root);
		if (this->back != NULL)
		{
			// Set last node of perorde
			this->back->left = NULL;
			this->back->right = NULL;
		}
		this->back = NULL;
	}
	//Display flatten elements of tree
	void show_element()
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree\n";
			return;
		}
		cout << "\n Flatten Tree Node in preorder : \n";
		Node *temp = this->root;
		//Iterate tree elements
		while (temp != NULL)
		{
			//Display node value
			cout << "  " << temp->data;
			//visit to next node
			temp = temp->right;
		}
	}
};
int main()
{
	//Make object of Binary Tree
	BinaryTree obj = BinaryTree();
	/*
	        Construct Binary Tree
	        -----------------------
	               1
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /   /   \   \
	        9   4    -6   11

	       
	        */
	//Add nodes
	obj.root = new Node(1);
	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->right->left = new Node(4);
	obj.root->left->left->left = new Node(9);
	obj.root->right->right->right = new Node(11);
	//Display tree elements
	cout << "\n Preorder Tree Nodes  : \n";
	obj.preorder(obj.root);
	//Perform transformation
	obj.transform();
	//After transform
	obj.show_element();;
	return 0;
}

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
//Include namespace system
using System;
/* 
  C# Program 
  Flatten a binary tree into 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 back;
	public BinaryTree()
	{
		//Set initial tree root to null
		this.root = null;
		this.back = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//This are flattening tree nodes in preorder from
	public void flatten_nodes(Node node)
	{
		if (node != null)
		{
			//Get right subtree of node
			Node right_side = node.right;
			if (this.back == null)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				this.back = node;
			}
			else
			{
				this.back.right = node;
				this.back.left = null;
				this.back = node;
			}
			//recursive executing left and right subtree
			flatten_nodes(node.left);
			flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	public void transform()
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		this.back = null;
		//Perform flatten operation
		flatten_nodes(this.root);
		if (this.back != null)
		{
			// Set last node of perorde
			this.back.left = null;
			this.back.right = null;
		}
		this.back = null;
	}
	//Display flatten elements of tree
	public void show_element()
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree\n");
			return;
		}
		Console.Write("\n Flatten Tree Node in preorder : \n");
		Node temp = this.root;
		//Iterate tree elements
		while (temp != null)
		{
			//Display node value
			Console.Write("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
	}
	public static void Main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/* 
		        Construct Binary Tree
		        -----------------------
		               1
		             /   \
		            6     8
		           / \   / \
		          2   3 7   5
		         /   /   \   \
		        9   4    -6   11

		       
		    */
		//Add nodes
		obj.root = new Node(1);
		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.right.left = new Node(4);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(11);
		//Display tree elements
		Console.Write("\n Preorder Tree Nodes  : \n");
		obj.preorder(obj.root);
		//Perform transformation
		obj.transform();
		//After transform
		obj.show_element();;
	}
}

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
<?php
/* 
  Php Program 
  Flatten a binary tree into 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 $back;

	function __construct()
	{
		//Set initial tree root to null
		$this->root = null;
		$this->back = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public	function preorder($node)
	{
		if ($node != null)
		{
			//Print node value
			echo "  ". $node->data;
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	//This are flattening tree nodes in preorder from
	public	function flatten_nodes($node)
	{
		if ($node != null)
		{
			//Get right subtree of node
			$right_side = $node->right;
			if ($this->back == null)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				$this->back = $node;
			}
			else
			{
				$this->back->right = $node;
				$this->back->left = null;
				$this->back = $node;
			}
			//recursive executing left and right subtree
			$this->flatten_nodes($node->left);
			$this->flatten_nodes($right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	public	function transform()
	{
		if ($this->root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		$this->back = null;
		//Perform flatten operation
		$this->flatten_nodes($this->root);
		if ($this->back != null)
		{
			// Set last node of perorde
			$this->back->left = null;
			$this->back->right = null;
		}
		$this->back = null;
	}
	//Display flatten elements of tree
	public	function show_element()
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree\n";
			return;
		}
		echo "\n Flatten Tree Node in preorder : \n";
		$temp = $this->root;
		//Iterate tree elements
		while ($temp != null)
		{
			//Display node value
			echo "  ". $temp->data;
			//visit to next node
			$temp = $temp->right;
		}
	}
}

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

	       
	    */
	//Add nodes
	$obj->root = new Node(1);
	$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->right->left = new Node(4);
	$obj->root->left->left->left = new Node(9);
	$obj->root->right->right->right = new Node(11);
	//Display tree elements
	echo "\n Preorder Tree Nodes  : \n";
	$obj->preorder($obj->root);
	//Perform transformation
	$obj->transform();
	//After transform
	$obj->show_element();;
}
main();

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
/* 
  Node Js Program 
  Flatten a binary tree into 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.back = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	preorder(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	//This are flattening tree nodes in preorder from
	flatten_nodes(node)
	{
		if (node != null)
		{
			//Get right subtree of node
			var right_side = node.right;
			if (this.back == null)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				this.back = node;
			}
			else
			{
				this.back.right = node;
				this.back.left = null;
				this.back = node;
			}
			//recursive executing left and right subtree
			this.flatten_nodes(node.left);
			this.flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	transform()
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		this.back = null;
		//Perform flatten operation
		this.flatten_nodes(this.root);
		if (this.back != null)
		{
			// Set last node of perorde
			this.back.left = null;
			this.back.right = null;
		}
		this.back = null;
	}
	//Display flatten elements of tree
	show_element()
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree\n");
			return;
		}
		process.stdout.write("\n Flatten Tree Node in preorder : \n");
		var temp = this.root;
		//Iterate tree elements
		while (temp != null)
		{
			//Display node value
			process.stdout.write("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
	}
}

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

	       
	    */
	//Add nodes
	obj.root = new Node(1);
	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.right.left = new Node(4);
	obj.root.left.left.left = new Node(9);
	obj.root.right.right.right = new Node(11);
	//Display tree elements
	process.stdout.write("\n Preorder Tree Nodes  : \n");
	obj.preorder(obj.root);
	//Perform transformation
	obj.transform();
	//After transform
	obj.show_element();;
}
main();

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
#   Python 3 Program 
#   Flatten a binary tree into 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
		self.back = None
	
	# Recursive function
	# Display preorder view of binary tree
	def preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	# This are flattening tree nodes in preorder from
	def flatten_nodes(self, node) :
		if (node != None) :
			# Get right subtree of node
			right_side = node.right
			if (self.back == None) :
				# This is first node of preorder traversal
				# Get first node of transform tree
				self.back = node
			else :
				self.back.right = node
				self.back.left = None
				self.back = node
			
			# recursive executing left and right subtree
			self.flatten_nodes(node.left)
			self.flatten_nodes(right_side)
		
	
	# This are handling the request of flatten tree nodes in perorde from
	def transform(self) :
		if (self.root == None) :
			#  When empty tree
			return
		
		#  Set back node
		self.back = None
		# Perform flatten operation
		self.flatten_nodes(self.root)
		if (self.back != None) :
			#  Set last node of perorde
			self.back.left = None
			self.back.right = None
		
		self.back = None
	
	# Display flatten elements of tree
	def show_element(self) :
		if (self.root == None) :
			print("\n Empty Tree\n", end = "")
			return
		
		print("\n Flatten Tree Node in preorder : \n", end = "")
		temp = self.root
		# Iterate tree elements
		while (temp != None) :
			# Display node value
			print("  ", temp.data, end = "")
			# visit to next node
			temp = temp.right
		
	

def main() :
	# Make object of Binary Tree
	obj = BinaryTree()
	#  
	#         Construct Binary Tree
	#         -----------------------
	#                1
	#              /   \
	#             6     8
	#            / \   / \
	#           2   3 7   5
	#          /   /   \   \
	#         9   4    -6   11
	#        
	#     
	
	# Add nodes
	obj.root = Node(1)
	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.right.left = Node(4)
	obj.root.left.left.left = Node(9)
	obj.root.right.right.right = Node(11)
	# Display tree elements
	print("\n Preorder Tree Nodes  : \n", end = "")
	obj.preorder(obj.root)
	# Perform transformation
	obj.transform()
	# After transform
	obj.show_element()

if __name__ == "__main__": main()

Output

 Preorder Tree Nodes  :
   1   6   2   9   3   4   8   7   -6   5   11
 Flatten Tree Node in preorder :
   1   6   2   9   3   4   8   7   -6   5   11
#   Ruby Program 
#   Flatten a binary tree into 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, :back
	attr_accessor :root, :back
 
	def initialize() 
		# Set initial tree root to null
		self.root = nil
		self.back = nil
	end
    
	# Recursive function
	# Display preorder view of binary tree
	def preorder(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.preorder(node.left)
			self.preorder(node.right)
		end
	end
    
	# This are flattening tree nodes in preorder from
	def flatten_nodes(node) 
		if (node != nil) 
			# Get right subtree of node
			right_side = node.right
			if (self.back == nil) 
				# This is first node of preorder traversal
				# Get first node of transform tree
				self.back = node
			else 
				self.back.right = node
				self.back.left = nil
				self.back = node
			end
			# recursive executing left and right subtree
			self.flatten_nodes(node.left)
			self.flatten_nodes(right_side)
		end
	end
    
	# This are handling the request of flatten tree nodes in perorde from
	def transform() 
		if (self.root == nil) 
			#  When empty tree
			return
		end
		#  Set back node
		self.back = nil
		# Perform flatten operation
		self.flatten_nodes(self.root)
		if (self.back != nil) 
			#  Set last node of perorde
			self.back.left = nil
			self.back.right = nil
		end
		self.back = nil
	end
    
	# Display flatten elements of tree
	def show_element() 
		if (self.root == nil) 
			print("\n Empty Tree\n")
			return
		end
		print("\n Flatten Tree Node in preorder : \n")
		temp = self.root
		# Iterate tree elements
		while (temp != nil) 
			# Display node value
			print("  ", temp.data)
			# visit to next node
			temp = temp.right
		end
	end
end
def main() 
	# Make object of Binary Tree
	obj = BinaryTree.new()
	#  
	#         Construct Binary Tree
	#         -----------------------
	#                1
	#              /   \
	#             6     8
	#            / \   / \
	#           2   3 7   5
	#          /   /   \   \
	#         9   4    -6   11
	#        
	#     
	
	# Add nodes
	obj.root = Node.new(1)
	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.right.left = Node.new(4)
	obj.root.left.left.left = Node.new(9)
	obj.root.right.right.right = Node.new(11)
	# Display tree elements
	print("\n Preorder Tree Nodes  : \n")
	obj.preorder(obj.root)
	# Perform transformation
	obj.transform()
	# After transform
	obj.show_element()
end
main()

Output

 Preorder Tree Nodes  : 
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder : 
  1  6  2  9  3  4  8  7  -6  5  11
/* 
  Scala Program 
  Flatten a binary tree into 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 back: Node)
{
	def this()
	{
		this(null, null);
	}
	//Recursive function
	//Display preorder view of binary tree
	def preorder(node: Node): Unit = {
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	//This are flattening tree nodes in preorder from
	def flatten_nodes(node: Node): Unit = {
		if (node != null)
		{
			//Get right subtree of node
			var right_side: Node = node.right;
			if (this.back == null)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				this.back = node;
			}
			else
			{
				this.back.right = node;
				this.back.left = null;
				this.back = node;
			}
			//recursive executing left and right subtree
			flatten_nodes(node.left);
			flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	def transform(): Unit = {
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		this.back = null;
		//Perform flatten operation
		flatten_nodes(this.root);
		if (this.back != null)
		{
			// Set last node of perorde
			this.back.left = null;
			this.back.right = null;
		}
		this.back = null;
	}
	//Display flatten elements of tree
	def show_element(): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree\n");
			return;
		}
		print("\n Flatten Tree Node in preorder : \n");
		var temp: Node = this.root;
		//Iterate tree elements
		while (temp != null)
		{
			//Display node value
			print("  " + temp.data);
			//visit to next node
			temp = temp.right;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of Binary Tree
		var obj: BinaryTree = new BinaryTree();
		/* 
		        Construct Binary Tree
		        -----------------------
		               1
		             /   \
		            6     8
		           / \   / \
		          2   3 7   5
		         /   /   \   \
		        9   4    -6   11

		       
		    */
		//Add nodes
		obj.root = new Node(1);
		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.right.left = new Node(4);
		obj.root.left.left.left = new Node(9);
		obj.root.right.right.right = new Node(11);
		//Display tree elements
		print("\n Preorder Tree Nodes  : \n");
		obj.preorder(obj.root);
		//Perform transformation
		obj.transform();
		//After transform
		obj.show_element();
	}
}

Output

 Preorder Tree Nodes  :
  1  6  2  9  3  4  8  7  -6  5  11
 Flatten Tree Node in preorder :
  1  6  2  9  3  4  8  7  -6  5  11
/* 
  Swift 4 Program 
  Flatten a binary tree into 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 back: Node? ;
	init()
	{
		//Set initial tree root to null
		self.root = nil;
		self.back = nil;
	}
	//Recursive function
	//Display preorder view of binary tree
	func preorder(_ node: Node? )
	{
		if (node != nil)
		{
			//Print node value
			print("  ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	//This are flattening tree nodes in preorder from
	func flatten_nodes(_ node: Node? )
	{
		if (node != nil)
		{
			//Get right subtree of node
			let right_side: Node? = node!.right;
			if (self.back == nil)
			{
				//This is first node of preorder traversal
				//Get first node of transform tree
				self.back = node;
			}
			else
			{
				self.back!.right = node;
				self.back!.left = nil;
				self.back = node;
			}
			//recursive executing left and right subtree
			self.flatten_nodes(node!.left);
			self.flatten_nodes(right_side);
		}
	}
	//This are handling the request of flatten tree nodes in perorde from
	func transform()
	{
		if (self.root == nil)
		{
			// When empty tree
			return;
		}
		// Set back node
		self.back = nil;
		//Perform flatten operation
		self.flatten_nodes(self.root);
		if (self.back != nil)
		{
			// Set last node of perorde
			self.back!.left = nil;
			self.back!.right = nil;
		}
		self.back = nil;
	}
	//Display flatten elements of tree
	func show_element()
	{
		if (self.root == nil)
		{
			print("\n Empty Tree\n", terminator: "");
			return;
		}
		print("\n Flatten Tree Node in preorder : \n", terminator: "");
		var temp: Node? = self.root;
		//Iterate tree elements
		while (temp != nil)
		{
			//Display node value
			print("  ", temp!.data, terminator: "");
			//visit to next node
			temp = temp!.right;
		}
	}
}
func main()
{
	//Make object of Binary Tree
	let obj: BinaryTree = BinaryTree();
	/* 
	        Construct Binary Tree
	        -----------------------
	               1
	             /   \
	            6     8
	           / \   / \
	          2   3 7   5
	         /   /   \   \
	        9   4    -6   11

	       
	    */
	//Add nodes
	obj.root = Node(1);
	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!.right!.left = Node(4);
	obj.root!.left!.left!.left = Node(9);
	obj.root!.right!.right!.right = Node(11);
	//Display tree elements
	print("\n Preorder Tree Nodes  : \n", terminator: "");
	obj.preorder(obj.root);
	//Perform transformation
	obj.transform();
	//After transform
	obj.show_element();
}
main();

Output

 Preorder Tree Nodes  :
   1   6   2   9   3   4   8   7   -6   5   11
 Flatten Tree Node in preorder :
   1   6   2   9   3   4   8   7   -6   5   11
Last updated on by Kalkicode




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