Posted on by Kalkicode
Code Tree

Implement Leftist Tree

Here given code implementation process.

``````/*
C Program
Implement Leftist Tree
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
int data;
int rank;
struct TreeNode *left;
struct TreeNode *right;
};

// Define structure of Leftist Tree
struct LeftistTree
{
struct TreeNode *root;
};
// Create new tree
struct LeftistTree *new_tree()
{
// Create dynamic node
struct LeftistTree *tree = (struct LeftistTree *) malloc(sizeof(struct LeftistTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *new_node(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->rank = 0;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
//Swap the child of given node
void swap_child(struct TreeNode *parent)
{
if (parent != NULL)
{
struct TreeNode *temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
//Merge nodes of given two leftist tree
struct TreeNode *merge_node(struct TreeNode *n1, struct TreeNode *n2)
{
if (n1 == NULL)
{
return n2;
}
if (n2 == NULL)
{
return n1;
}
if (n1->data < n2->data)
{
// When need to Modification in first leftist tree
if (n1->left == NULL)
{
//When left subtree null
n1->left = n2;
}
else
{
n1->right = merge_node(n1->right, n2);
if (n1->left->rank < n1->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1->right != NULL)
{
// Update the current path node rank
n1->rank = n1->right->rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2->left == NULL)
{
//When left subtree null
n2->left = n1;
}
else
{
n2->right = merge_node(n2->right, n1);
if (n2->left->rank < n2->right->rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2->right != NULL)
{
// Update the current path node rank
n2->rank = n2->right->rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
void add_node(struct LeftistTree *tree, int data)
{
struct TreeNode *node = new_node(data);
tree->root = merge_node(node, tree->root);
}
void inorder(struct TreeNode *node)
{
if (node != NULL)
{
inorder(node->left);
//Print node value
printf("  %d", node->data);
inorder(node->right);
}
}
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
//Print node value
printf("  %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(struct TreeNode *node)
{
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
//Print node value
printf("  %d", node->data);
}
}
// Handles the request of view tree elements
void print_tree(struct LeftistTree *tree)
{
if (tree->root != NULL)
{
// Display tree elements
printf("\n Preorder : ");
preorder(tree->root);
printf("\n Inorder : ");
inorder(tree->root);
printf("\n Postorder : ");
postorder(tree->root);
printf("\n");
}
else
{
printf("\n Empty Tree");
}
}
//Handles the request to merge two trees
void merge_tree(struct LeftistTree *tree1, struct LeftistTree *tree2)
{
tree1->root = merge_node(tree1->root, tree2->root);
tree2->root = NULL;
}
void delete_min(struct LeftistTree *tree)
{
if (tree->root == NULL)
{
printf("\nEmpty Tree\n");
}
else
{
tree->root = merge_node(tree->root->left, tree->root->right);
}
}
//Print Min element of tree
void min_element(struct LeftistTree *tree)
{
if (tree->root == NULL)
{
printf("\nEmpty Tree\n");
}
else
{
printf("\n Min Element : %d \n", tree->root->data);
}
}
int main()
{
struct LeftistTree *tree1 = new_tree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
print_tree(tree1);
struct LeftistTree *tree2 = new_tree();
// Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
print_tree(tree2);
printf("\n Merge Two Tree \n");
merge_tree(tree1, tree2);
//After merge two tree
printf("\n Tree 1");
print_tree(tree1);
printf("\n Tree 2");
print_tree(tree2);
printf("\n\n Delete Min ");
min_element(tree1);
delete_min(tree1);
print_tree(tree1);
return 0;
}``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````/*
Java Program
Implement Leftist Tree
*/

// Tree Node
class TreeNode
{
public int data;
public int rank;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}

// Leftist Tree
public class LeftistTree
{
public TreeNode root;
public LeftistTree()
{
this.root = null;
}
//Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
//Merge nodes of given two leftist tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
// When need to Modification in first leftist tree
if (n1.left == null)
{
//When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
// Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
// When need to Modification in second leftist tree
if (n2.left == null)
{
//When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
// When rank of left subtree is less than of right subtree.
// Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
// Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
// Handles the request of adding a new node in leftist tree
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
//Print node value
System.out.print("  " + node.data );
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
//Print node value
System.out.print("  " + node.data );
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
//Print node value
System.out.print("  " + node.data );
}
}
// Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
// Display tree elements
System.out.print("\n Preorder : ");
preorder(this.root);
System.out.print("\n Inorder : ");
inorder(this.root);
System.out.print("\n Postorder : ");
postorder(this.root);
System.out.print("\n");
}
else
{
System.out.print("\n Empty Tree");
}
}
//Handles the request to merge two trees
public void merge_tree(LeftistTree tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
//Print Min element of tree
public void min_element()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
System.out.print("\n Min Element : " + this.root.data + " \n");
}
}
public static void main(String[] args)
{
LeftistTree tree1 = new LeftistTree();
LeftistTree tree2 = new LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
// Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
System.out.print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
//After merge two tree
System.out.print("\n Tree 1");
tree1.print_tree();
System.out.print("\n Tree 2");
tree2.print_tree();
System.out.print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Implement Leftist Tree
*/

//  Tree Node
class TreeNode
{
public:
int data;
int rank;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->rank = 0;
this->left = NULL;
this->right = NULL;
}
};
//  Leftist Tree
class LeftistTree
{
public:
TreeNode *root;
LeftistTree()
{
this->root = NULL;
}
// Swap the child of given node
void swap_child(TreeNode *parent)
{
if (parent != NULL)
{
TreeNode *temp = parent->left;
parent->left = parent->right;
parent->right = temp;
}
}
// Merge nodes of given two leftist tree
TreeNode *merge_node(TreeNode *n1, TreeNode *n2)
{
if (n1 == NULL)
{
return n2;
}
if (n2 == NULL)
{
return n1;
}
if (n1->data < n2->data)
{
//  When need to Modification in first leftist tree
if (n1->left == NULL)
{
// When left subtree null
n1->left = n2;
}
else
{
n1->right = this->merge_node(n1->right, n2);
if (n1->left->rank < n1->right->rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
this->swap_child(n1);
}
}
if (n1->right != NULL)
{
//  Update the current path node rank
n1->rank = n1->right->rank + 1;
}
return n1;
}
else
{
//  When need to Modification in second leftist tree
if (n2->left == NULL)
{
// When left subtree null
n2->left = n1;
}
else
{
n2->right = this->merge_node(n2->right, n1);
if (n2->left->rank < n2->right->rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
this->swap_child(n2);
}
}
if (n2->right != NULL)
{
//  Update the current path node rank
n2->rank = n2->right->rank + 1;
}
return n2;
}
}
//  Handles the request of adding a new node in leftist tree
{
TreeNode *node = new TreeNode(data);
this->root = this->merge_node(node, this->root);
}
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
// Print node value
cout << "  " << node->data;
this->inorder(node->right);
}
}
void preorder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << "  " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
void postorder(TreeNode *node)
{
if (node != NULL)
{
this->postorder(node->left);
this->postorder(node->right);
// Print node value
cout << "  " << node->data;
}
}
//  Handles the request of view tree elements
void print_tree()
{
if (this->root != NULL)
{
//  Display tree elements
cout << "\n Preorder : ";
this->preorder(this->root);
cout << "\n Inorder : ";
this->inorder(this->root);
cout << "\n Postorder : ";
this->postorder(this->root);
cout << "\n";
}
else
{
cout << "\n Empty Tree";
}
}
// Handles the request to merge two trees
void merge_tree(LeftistTree tree2)
{
this->root = this->merge_node(this->root, tree2.root);
tree2.root = NULL;
}
void delete_min()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
this->root = this->merge_node(this->root->left, this->root->right);
}
}
// Print Min element of tree
void min_element()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
cout << "\n Min Element : " << this->root->data << " \n";
}
}
};
int main()
{
LeftistTree tree1 = LeftistTree();
LeftistTree tree2 = LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
cout << "\n Merge Two Tree \n";
tree1.merge_tree(tree2);
// After merge two tree
cout << "\n Tree 1";
tree1.print_tree();
cout << "\n Tree 2";
tree2.print_tree();
cout << "\n\n Delete Min ";
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
return 0;
}``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````// Include namespace system
using System;

/*
C# Program
Implement Leftist Tree
*/

//  Tree Node
public class TreeNode
{
public int data;
public int rank;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}
//  Leftist Tree
public class LeftistTree
{
public TreeNode root;
public LeftistTree()
{
this.root = null;
}
// Swap the child of given node
public void swap_child(TreeNode parent)
{
if (parent != null)
{
TreeNode temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
public TreeNode merge_node(TreeNode n1, TreeNode n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
//  When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
//  Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
//  When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
//  Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
//  Handles the request of adding a new node in leftist tree
{
TreeNode node = new TreeNode(data);
this.root = merge_node(node, this.root);
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Print node value
Console.Write("  " + node.data);
inorder(node.right);
}
}
public void preorder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write("  " + node.data);
preorder(node.left);
preorder(node.right);
}
}
public void postorder(TreeNode node)
{
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
Console.Write("  " + node.data);
}
}
//  Handles the request of view tree elements
public void print_tree()
{
if (this.root != null)
{
//  Display tree elements
Console.Write("\n Preorder : ");
preorder(this.root);
Console.Write("\n Inorder : ");
inorder(this.root);
Console.Write("\n Postorder : ");
postorder(this.root);
Console.Write("\n");
}
else
{
Console.Write("\n Empty Tree");
}
}
// Handles the request to merge two trees
public void merge_tree(LeftistTree tree2)
{
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
public void delete_min()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
public void min_element()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
Console.Write("\n Min Element : " + this.root.data + " \n");
}
}
public static void Main(String[] args)
{
LeftistTree tree1 = new LeftistTree();
LeftistTree tree2 = new LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
Console.Write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
Console.Write("\n Tree 1");
tree1.print_tree();
Console.Write("\n Tree 2");
tree2.print_tree();
Console.Write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````<?php
/*
Php Program
Implement Leftist Tree
*/
//  Tree Node
class TreeNode
{
public \$data;
public \$rank;
public \$left;
public \$right;

function __construct(\$data)
{
\$this->data = \$data;
\$this->rank = 0;
\$this->left = null;
\$this->right = null;
}
}
//  Leftist Tree
class LeftistTree
{
public \$root;

function __construct()
{
\$this->root = null;
}
// Swap the child of given node
public  function swap_child(\$parent)
{
if (\$parent != null)
{
\$temp = \$parent->left;
\$parent->left = \$parent->right;
\$parent->right = \$temp;
}
}
// Merge nodes of given two leftist tree
public  function merge_node(\$n1, \$n2)
{
if (\$n1 == null)
{
return \$n2;
}
if (\$n2 == null)
{
return \$n1;
}
if (\$n1->data < \$n2->data)
{
//  When need to Modification in first leftist tree
if (\$n1->left == null)
{
// When left subtree null
\$n1->left = \$n2;
}
else
{
\$n1->right = \$this->merge_node(\$n1->right, \$n2);
if (\$n1->left->rank < \$n1->right->rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
\$this->swap_child(\$n1);
}
}
if (\$n1->right != null)
{
//  Update the current path node rank
\$n1->rank = \$n1->right->rank + 1;
}
return \$n1;
}
else
{
//  When need to Modification in second leftist tree
if (\$n2->left == null)
{
// When left subtree null
\$n2->left = \$n1;
}
else
{
\$n2->right = \$this->merge_node(\$n2->right, \$n1);
if (\$n2->left->rank < \$n2->right->rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
\$this->swap_child(\$n2);
}
}
if (\$n2->right != null)
{
//  Update the current path node rank
\$n2->rank = \$n2->right->rank + 1;
}
return \$n2;
}
}
//  Handles the request of adding a new node in leftist tree
{
\$node = new TreeNode(\$data);
\$this->root = \$this->merge_node(\$node, \$this->root);
}
public  function inorder(\$node)
{
if (\$node != null)
{
\$this->inorder(\$node->left);
// Print node value
echo "  ". \$node->data;
\$this->inorder(\$node->right);
}
}
public  function preorder(\$node)
{
if (\$node != null)
{
// Print node value
echo "  ". \$node->data;
\$this->preorder(\$node->left);
\$this->preorder(\$node->right);
}
}
public  function postorder(\$node)
{
if (\$node != null)
{
\$this->postorder(\$node->left);
\$this->postorder(\$node->right);
// Print node value
echo "  ". \$node->data;
}
}
//  Handles the request of view tree elements
public  function print_tree()
{
if (\$this->root != null)
{
//  Display tree elements
echo "\n Preorder : ";
\$this->preorder(\$this->root);
echo "\n Inorder : ";
\$this->inorder(\$this->root);
echo "\n Postorder : ";
\$this->postorder(\$this->root);
echo "\n";
}
else
{
echo "\n Empty Tree";
}
}
// Handles the request to merge two trees
public  function merge_tree(\$tree2)
{
\$this->root = \$this->merge_node(\$this->root, \$tree2->root);
\$tree2->root = null;
}
public  function delete_min()
{
if (\$this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
\$this->root = \$this->merge_node(\$this->root->left, \$this->root->right);
}
}
// Print Min element of tree
public  function min_element()
{
if (\$this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
echo "\n Min Element : ". \$this->root->data ." \n";
}
}
}

function main()
{
\$tree1 = new LeftistTree();
\$tree2 = new LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
\$tree1->print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
\$tree2->print_tree();
echo "\n Merge Two Tree \n";
\$tree1->merge_tree(\$tree2);
// After merge two tree
echo "\n Tree 1";
\$tree1->print_tree();
echo "\n Tree 2";
\$tree2->print_tree();
echo "\n\n Delete Min ";
\$tree1->min_element();
\$tree1->delete_min();
\$tree1->print_tree();
}
main();``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````/*
Node Js Program
Implement Leftist Tree
*/

//  Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.rank = 0;
this.left = null;
this.right = null;
}
}
//  Leftist Tree
class LeftistTree
{
constructor()
{
this.root = null;
}
// Swap the child of given node
swap_child(parent)
{
if (parent != null)
{
var temp = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
merge_node(n1, n2)
{
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
//  When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = this.merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
this.swap_child(n1);
}
}
if (n1.right != null)
{
//  Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
//  When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = this.merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
this.swap_child(n2);
}
}
if (n2.right != null)
{
//  Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
//  Handles the request of adding a new node in leftist tree
{
var node = new TreeNode(data);
this.root = this.merge_node(node, this.root);
}
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
// Print node value
process.stdout.write("  " + node.data);
this.inorder(node.right);
}
}
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write("  " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
postorder(node)
{
if (node != null)
{
this.postorder(node.left);
this.postorder(node.right);
// Print node value
process.stdout.write("  " + node.data);
}
}
//  Handles the request of view tree elements
print_tree()
{
if (this.root != null)
{
//  Display tree elements
process.stdout.write("\n Preorder : ");
this.preorder(this.root);
process.stdout.write("\n Inorder : ");
this.inorder(this.root);
process.stdout.write("\n Postorder : ");
this.postorder(this.root);
process.stdout.write("\n");
}
else
{
process.stdout.write("\n Empty Tree");
}
}
// Handles the request to merge two trees
merge_tree(tree2)
{
this.root = this.merge_node(this.root, tree2.root);
tree2.root = null;
}
delete_min()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
this.root = this.merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
min_element()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
process.stdout.write("\n Min Element : " + this.root.data + " \n");
}
}
}

function main()
{
var tree1 = new LeftistTree();
var tree2 = new LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
process.stdout.write("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
process.stdout.write("\n Tree 1");
tree1.print_tree();
process.stdout.write("\n Tree 2");
tree2.print_tree();
process.stdout.write("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
main();``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````#  Python 3 Program
#  Implement Leftist Tree

#  Tree Node
class TreeNode :

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

#  Leftist Tree
class LeftistTree :

def __init__(self) :
self.root = None

# Swap the child of given node
def swap_child(self, parent) :
if (parent != None) :
temp = parent.left
parent.left = parent.right
parent.right = temp

# Merge nodes of given two leftist tree
def merge_node(self, n1, n2) :
if (n1 == None) :
return n2

if (n2 == None) :
return n1

if (n1.data < n2.data) :
#  When need to Modification in first leftist tree
if (n1.left == None) :
# When left subtree null
n1.left = n2
else :
n1.right = self.merge_node(n1.right, n2)
if (n1.left.rank < n1.right.rank) :
#  When rank of left subtree is less than of right subtree.
#  Then change the position of subtree
self.swap_child(n1)

if (n1.right != None) :
#  Update the current path node rank
n1.rank = n1.right.rank + 1

return n1
else :
#  When need to Modification in second leftist tree
if (n2.left == None) :
# When left subtree null
n2.left = n1
else :
n2.right = self.merge_node(n2.right, n1)
if (n2.left.rank < n2.right.rank) :
#  When rank of left subtree is less than of right subtree.
#  Then change the position of subtree
self.swap_child(n2)

if (n2.right != None) :
#  Update the current path node rank
n2.rank = n2.right.rank + 1

return n2

#  Handles the request of adding a new node in leftist tree
node = TreeNode(data)
self.root = self.merge_node(node, self.root)

def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
# Print node value
print("  ", node.data, end = "")
self.inorder(node.right)

def preorder(self, node) :
if (node != None) :
# Print node value
print("  ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)

def postorder(self, node) :
if (node != None) :
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print("  ", node.data, end = "")

#  Handles the request of view tree elements
def print_tree(self) :
if (self.root != None) :
#  Display tree elements
print("\n Preorder : ", end = "")
self.preorder(self.root)
print("\n Inorder : ", end = "")
self.inorder(self.root)
print("\n Postorder : ", end = "")
self.postorder(self.root)
print("\n", end = "")
else :
print("\n Empty Tree", end = "")

# Handles the request to merge two trees
def merge_tree(self, tree2) :
self.root = self.merge_node(self.root, tree2.root)
tree2.root = None

def delete_min(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
self.root = self.merge_node(self.root.left, self.root.right)

# Print Min element of tree
def min_element(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
print("\n Min Element : ", self.root.data ," \n", end = "")

def main() :
tree1 = LeftistTree()
tree2 = LeftistTree()
#
#                   2
#                 /  \
#                /    \
#               4      3
#              / \    /
#             45  13 6
#            /      / \
#           70     9   11
#         ----------------------------
#         Constructing Leftist Tree
#         ----------------------------
#         Node [2], Rank (1)
#         Node [4], Rank (1)
#         Node [45], Rank (0)
#         Node [70], Rank (0)
#         Node [13], Rank (0)
#         Node [3], Rank (0)
#         Node [6], Rank (1)
#         Node [9], Rank (0)
#         Node [11], Rank (0)
#         ----------------------------
#

tree1.print_tree()
#  Put tree nodes
#
#               5
#             /   \
#            /     \
#           8       9
#          / \     / \
#         41  12 100  50
#                / \
#             120   150
#         ----------------------------
#         Constructing Leftist Tree
#         ----------------------------
#         Node [5], Rank (2)
#         Node [8], Rank (1)
#         Node [41], Rank (0)
#         Node [12], Rank (0)
#         Node [9], Rank (1)
#         Node [100], Rank (1)
#         Node [120], Rank (0)
#         Node [150], Rank (0)
#         Node [50], Rank (0)
#         ------------------
#

tree2.print_tree()
print("\n Merge Two Tree \n", end = "")
tree1.merge_tree(tree2)
# After merge two tree
print("\n Tree 1", end = "")
tree1.print_tree()
print("\n Tree 2", end = "")
tree2.print_tree()
print("\n\n Delete Min ", end = "")
tree1.min_element()
tree1.delete_min()
tree1.print_tree()

if __name__ == "__main__": main()``````

Output

`````` Preorder :    2   4   45   70   13   3   6   9   11
Inorder :    70   45   4   13   2   9   6   11   3
Postorder :    70   45   13   4   9   11   6   3   2

Preorder :    5   8   41   12   9   100   120   150   50
Inorder :    41   8   12   5   120   100   150   9   50
Postorder :    41   12   8   120   150   100   50   9   5

Merge Two Tree

Tree 1
Preorder :    2   3   5   8   41   12   9   100   120   150   50   6   9   11   4   45   70   13
Inorder :    41   8   12   5   120   100   150   9   50   3   9   6   11   2   70   45   4   13
Postorder :    41   12   8   120   150   100   50   9   5   9   11   6   3   70   45   13   4   2

Tree 2
Empty Tree

Delete Min
Min Element :  2

Preorder :    3   5   8   41   12   9   100   120   150   50   4   6   9   11   13   45   70
Inorder :    41   8   12   5   120   100   150   9   50   3   9   6   13   11   4   70   45
Postorder :    41   12   8   120   150   100   50   9   5   9   13   11   6   70   45   4   3``````
``````#  Ruby Program
#  Implement Leftist Tree

#  Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :rank, :left, :right

def initialize(data)
self.data = data
self.rank = 0
self.left = nil
self.right = nil
end

end

#  Leftist Tree
class LeftistTree
# Define the accessor and reader of class LeftistTree
attr_accessor :root

def initialize()
self.root = nil
end

# Swap the child of given node
def swap_child(parent)
if (parent != nil)
temp = parent.left
parent.left = parent.right
parent.right = temp
end

end

# Merge nodes of given two leftist tree
def merge_node(n1, n2)
if (n1 == nil)
return n2
end

if (n2 == nil)
return n1
end

if (n1.data < n2.data)
#  When need to Modification in first leftist tree
if (n1.left == nil)
# When left subtree null
n1.left = n2
else
n1.right = self.merge_node(n1.right, n2)
if (n1.left.rank < n1.right.rank)
#  When rank of left subtree is less than of right subtree.
#  Then change the position of subtree
self.swap_child(n1)
end

end

if (n1.right != nil)
#  Update the current path node rank
n1.rank = n1.right.rank + 1
end

return n1
else
#  When need to Modification in second leftist tree
if (n2.left == nil)
# When left subtree null
n2.left = n1
else
n2.right = self.merge_node(n2.right, n1)
if (n2.left.rank < n2.right.rank)
#  When rank of left subtree is less than of right subtree.
#  Then change the position of subtree
self.swap_child(n2)
end

end

if (n2.right != nil)
#  Update the current path node rank
n2.rank = n2.right.rank + 1
end

return n2
end

end

#  Handles the request of adding a new node in leftist tree
node = TreeNode.new(data)
self.root = self.merge_node(node, self.root)
end

def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print("  ", node.data)
self.inorder(node.right)
end

end

def preorder(node)
if (node != nil)
# Print node value
print("  ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end

end

def postorder(node)
if (node != nil)
self.postorder(node.left)
self.postorder(node.right)
# Print node value
print("  ", node.data)
end

end

#  Handles the request of view tree elements
def print_tree()
if (self.root != nil)
#  Display tree elements
print("\n Preorder : ")
self.preorder(self.root)
print("\n Inorder : ")
self.inorder(self.root)
print("\n Postorder : ")
self.postorder(self.root)
print("\n")
else
print("\n Empty Tree")
end

end

# Handles the request to merge two trees
def merge_tree(tree2)
self.root = self.merge_node(self.root, tree2.root)
tree2.root = nil
end

def delete_min()
if (self.root == nil)
print("\nEmpty Tree\n")
else
self.root = self.merge_node(self.root.left, self.root.right)
end

end

# Print Min element of tree
def min_element()
if (self.root == nil)
print("\nEmpty Tree\n")
else
print("\n Min Element : ", self.root.data ," \n")
end

end

end

def main()
tree1 = LeftistTree.new()
tree2 = LeftistTree.new()
#
#                   2
#                 /  \
#                /    \
#               4      3
#              / \    /
#             45  13 6
#            /      / \
#           70     9   11
#         ----------------------------
#         Constructing Leftist Tree
#         ----------------------------
#         Node [2], Rank (1)
#         Node [4], Rank (1)
#         Node [45], Rank (0)
#         Node [70], Rank (0)
#         Node [13], Rank (0)
#         Node [3], Rank (0)
#         Node [6], Rank (1)
#         Node [9], Rank (0)
#         Node [11], Rank (0)
#         ----------------------------
#

tree1.print_tree()
#  Put tree nodes
#
#               5
#             /   \
#            /     \
#           8       9
#          / \     / \
#         41  12 100  50
#                / \
#             120   150
#         ----------------------------
#         Constructing Leftist Tree
#         ----------------------------
#         Node [5], Rank (2)
#         Node [8], Rank (1)
#         Node [41], Rank (0)
#         Node [12], Rank (0)
#         Node [9], Rank (1)
#         Node [100], Rank (1)
#         Node [120], Rank (0)
#         Node [150], Rank (0)
#         Node [50], Rank (0)
#         ------------------
#

tree2.print_tree()
print("\n Merge Two Tree \n")
tree1.merge_tree(tree2)
# After merge two tree
print("\n Tree 1")
tree1.print_tree()
print("\n Tree 2")
tree2.print_tree()
print("\n\n Delete Min ")
tree1.min_element()
tree1.delete_min()
tree1.print_tree()
end

main()``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3
``````
``````/*
Scala Program
Implement Leftist Tree
*/
//  Tree Node
class TreeNode(var data: Int , var rank: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, 0, null, null);
}
}
//  Leftist Tree
class LeftistTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Swap the child of given node
def swap_child(parent: TreeNode): Unit = {
if (parent != null)
{
var temp: TreeNode = parent.left;
parent.left = parent.right;
parent.right = temp;
}
}
// Merge nodes of given two leftist tree
def merge_node(n1: TreeNode, n2: TreeNode): TreeNode = {
if (n1 == null)
{
return n2;
}
if (n2 == null)
{
return n1;
}
if (n1.data < n2.data)
{
//  When need to Modification in first leftist tree
if (n1.left == null)
{
// When left subtree null
n1.left = n2;
}
else
{
n1.right = merge_node(n1.right, n2);
if (n1.left.rank < n1.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
swap_child(n1);
}
}
if (n1.right != null)
{
//  Update the current path node rank
n1.rank = n1.right.rank + 1;
}
return n1;
}
else
{
//  When need to Modification in second leftist tree
if (n2.left == null)
{
// When left subtree null
n2.left = n1;
}
else
{
n2.right = merge_node(n2.right, n1);
if (n2.left.rank < n2.right.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
swap_child(n2);
}
}
if (n2.right != null)
{
//  Update the current path node rank
n2.rank = n2.right.rank + 1;
}
return n2;
}
}
//  Handles the request of adding a new node in leftist tree
def add_node(data: Int): Unit = {
var node: TreeNode = new TreeNode(data);
this.root = merge_node(node, this.root);
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
// Print node value
print("  " + node.data);
inorder(node.right);
}
}
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print("  " + node.data);
preorder(node.left);
preorder(node.right);
}
}
def postorder(node: TreeNode): Unit = {
if (node != null)
{
postorder(node.left);
postorder(node.right);
// Print node value
print("  " + node.data);
}
}
//  Handles the request of view tree elements
def print_tree(): Unit = {
if (this.root != null)
{
//  Display tree elements
print("\n Preorder : ");
preorder(this.root);
print("\n Inorder : ");
inorder(this.root);
print("\n Postorder : ");
postorder(this.root);
print("\n");
}
else
{
print("\n Empty Tree");
}
}
// Handles the request to merge two trees
def merge_tree(tree2: LeftistTree): Unit = {
this.root = merge_node(this.root, tree2.root);
tree2.root = null;
}
def delete_min(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
this.root = merge_node(this.root.left, this.root.right);
}
}
// Print Min element of tree
def min_element(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
print("\n Min Element : " + this.root.data + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: LeftistTree = new LeftistTree();
var tree2: LeftistTree = new LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
print("\n Merge Two Tree \n");
tree1.merge_tree(tree2);
// After merge two tree
print("\n Tree 1");
tree1.print_tree();
print("\n Tree 2");
tree2.print_tree();
print("\n\n Delete Min ");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
}``````

Output

`````` Preorder :   2  4  45  70  13  3  6  9  11
Inorder :   70  45  4  13  2  9  6  11  3
Postorder :   70  45  13  4  9  11  6  3  2

Preorder :   5  8  41  12  9  100  120  150  50
Inorder :   41  8  12  5  120  100  150  9  50
Postorder :   41  12  8  120  150  100  50  9  5

Merge Two Tree

Tree 1
Preorder :   2  3  5  8  41  12  9  100  120  150  50  6  9  11  4  45  70  13
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  11  2  70  45  4  13
Postorder :   41  12  8  120  150  100  50  9  5  9  11  6  3  70  45  13  4  2

Tree 2
Empty Tree

Delete Min
Min Element : 2

Preorder :   3  5  8  41  12  9  100  120  150  50  4  6  9  11  13  45  70
Inorder :   41  8  12  5  120  100  150  9  50  3  9  6  13  11  4  70  45
Postorder :   41  12  8  120  150  100  50  9  5  9  13  11  6  70  45  4  3``````
``````/*
Swift 4 Program
Implement Leftist Tree
*/
//  Tree Node
class TreeNode
{
var data: Int;
var rank: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.rank = 0;
self.left = nil;
self.right = nil;
}
}
//  Leftist Tree
class LeftistTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Swap the child of given node
func swap_child(_ parent: TreeNode? )
{
if (parent != nil)
{
let temp: TreeNode? = parent!.left;
parent!.left = parent!.right;
parent!.right = temp;
}
}
// Merge nodes of given two leftist tree
func merge_node(_ n1: TreeNode? , _ n2 : TreeNode? )->TreeNode?
{
if (n1 == nil)
{
return n2;
}
if (n2 == nil)
{
return n1;
}
if (n1!.data < n2!.data)
{
//  When need to Modification in first leftist tree
if (n1!.left == nil)
{
// When left subtree null
n1!.left = n2;
}
else
{
n1!.right = self.merge_node(n1!.right, n2);
if (n1!.left!.rank < n1!.right!.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
self.swap_child(n1);
}
}
if (n1!.right != nil)
{
//  Update the current path node rank
n1!.rank = n1!.right!.rank + 1;
}
return n1;
}
else
{
//  When need to Modification in second leftist tree
if (n2!.left == nil)
{
// When left subtree null
n2!.left = n1;
}
else
{
n2!.right = self.merge_node(n2!.right, n1);
if (n2!.left!.rank < n2!.right!.rank)
{
//  When rank of left subtree is less than of right subtree.
//  Then change the position of subtree
self.swap_child(n2);
}
}
if (n2!.right != nil)
{
//  Update the current path node rank
n2!.rank = n2!.right!.rank + 1;
}
return n2;
}
}
//  Handles the request of adding a new node in leftist tree
{
let node: TreeNode? = TreeNode(data);
self.root = self.merge_node(node, self.root);
}
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
// Print node value
print("  ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
func preorder(_ node: TreeNode? )
{
if (node != nil)
{
// Print node value
print("  ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func postorder(_ node: TreeNode? )
{
if (node != nil)
{
self.postorder(node!.left);
self.postorder(node!.right);
// Print node value
print("  ", node!.data, terminator: "");
}
}
//  Handles the request of view tree elements
func print_tree()
{
if (self.root != nil)
{
//  Display tree elements
print("\n Preorder : ", terminator: "");
self.preorder(self.root);
print("\n Inorder : ", terminator: "");
self.inorder(self.root);
print("\n Postorder : ", terminator: "");
self.postorder(self.root);
print("\n", terminator: "");
}
else
{
print("\n Empty Tree", terminator: "");
}
}
// Handles the request to merge two trees
func merge_tree(_ tree2: LeftistTree? )
{
self.root = self.merge_node(self.root, tree2!.root);
tree2!.root = nil;
}
func delete_min()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
self.root = self.merge_node(self.root!.left, self.root!.right);
}
}
// Print Min element of tree
func min_element()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
print("\n Min Element : ", self.root!.data ," \n", terminator: "");
}
}
}
func main()
{
let tree1: LeftistTree = LeftistTree();
let tree2: LeftistTree = LeftistTree();
/*

2
/  \
/    \
4      3
/ \    /
45  13 6
/      / \
70     9   11
----------------------------
Constructing Leftist Tree
----------------------------
Node [2], Rank (1)
Node [4], Rank (1)
Node [45], Rank (0)
Node [70], Rank (0)
Node [13], Rank (0)
Node [3], Rank (0)
Node [6], Rank (1)
Node [9], Rank (0)
Node [11], Rank (0)
----------------------------
*/
tree1.print_tree();
//  Put tree nodes
/*

5
/   \
/     \
8       9
/ \     / \
41  12 100  50
/ \
120   150
----------------------------
Constructing Leftist Tree
----------------------------
Node [5], Rank (2)
Node [8], Rank (1)
Node [41], Rank (0)
Node [12], Rank (0)
Node [9], Rank (1)
Node [100], Rank (1)
Node [120], Rank (0)
Node [150], Rank (0)
Node [50], Rank (0)
------------------

*/
tree2.print_tree();
print("\n Merge Two Tree \n", terminator: "");
tree1.merge_tree(tree2);
// After merge two tree
print("\n Tree 1", terminator: "");
tree1.print_tree();
print("\n Tree 2", terminator: "");
tree2.print_tree();
print("\n\n Delete Min ", terminator: "");
tree1.min_element();
tree1.delete_min();
tree1.print_tree();
}
main();``````

Output

`````` Preorder :    2   4   45   70   13   3   6   9   11
Inorder :    70   45   4   13   2   9   6   11   3
Postorder :    70   45   13   4   9   11   6   3   2

Preorder :    5   8   41   12   9   100   120   150   50
Inorder :    41   8   12   5   120   100   150   9   50
Postorder :    41   12   8   120   150   100   50   9   5

Merge Two Tree

Tree 1
Preorder :    2   3   5   8   41   12   9   100   120   150   50   6   9   11   4   45   70   13
Inorder :    41   8   12   5   120   100   150   9   50   3   9   6   11   2   70   45   4   13
Postorder :    41   12   8   120   150   100   50   9   5   9   11   6   3   70   45   13   4   2

Tree 2
Empty Tree

Delete Min
Min Element :  2

Preorder :    3   5   8   41   12   9   100   120   150   50   4   6   9   11   13   45   70
Inorder :    41   8   12   5   120   100   150   9   50   3   9   6   13   11   4   70   45
Postorder :    41   12   8   120   150   100   50   9   5   9   13   11   6   70   45   4   3``````

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.

Categories
Relative Post