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();
    // Added nodes
    add_node(tree1, 6);
    add_node(tree1, 9);
    add_node(tree1, 11);
    add_node(tree1, 3);
    add_node(tree1, 2);
    add_node(tree1, 45);
    add_node(tree1, 70);
    add_node(tree1, 4);
    add_node(tree1, 13);
    /*

              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
    add_node(tree2, 5);
    add_node(tree2, 9);
    add_node(tree2, 41);
    add_node(tree2, 8);
    add_node(tree2, 12);
    add_node(tree2, 50);
    add_node(tree2, 100);
    add_node(tree2, 120);
    add_node(tree2, 150);
    /*

          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
    public void add_node(int data)
    {
        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();
        // Added nodes
        tree1.add_node(6);
        tree1.add_node(9);
        tree1.add_node(11);
        tree1.add_node(3);
        tree1.add_node(2);
        tree1.add_node(45);
        tree1.add_node(70);
        tree1.add_node(4);
        tree1.add_node(13);
        /*

                  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
        tree2.add_node(5);
        tree2.add_node(9);
        tree2.add_node(41);
        tree2.add_node(8);
        tree2.add_node(12);
        tree2.add_node(50);
        tree2.add_node(100);
        tree2.add_node(120);
        tree2.add_node(150);
        /*

              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
    void add_node(int data)
    {
        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();
    //  Added nodes
    tree1.add_node(6);
    tree1.add_node(9);
    tree1.add_node(11);
    tree1.add_node(3);
    tree1.add_node(2);
    tree1.add_node(45);
    tree1.add_node(70);
    tree1.add_node(4);
    tree1.add_node(13);
    /*

                      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
    tree2.add_node(5);
    tree2.add_node(9);
    tree2.add_node(41);
    tree2.add_node(8);
    tree2.add_node(12);
    tree2.add_node(50);
    tree2.add_node(100);
    tree2.add_node(120);
    tree2.add_node(150);
    /*

                  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
    public void add_node(int data)
    {
        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();
        //  Added nodes
        tree1.add_node(6);
        tree1.add_node(9);
        tree1.add_node(11);
        tree1.add_node(3);
        tree1.add_node(2);
        tree1.add_node(45);
        tree1.add_node(70);
        tree1.add_node(4);
        tree1.add_node(13);
        /*

                  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
        tree2.add_node(5);
        tree2.add_node(9);
        tree2.add_node(41);
        tree2.add_node(8);
        tree2.add_node(12);
        tree2.add_node(50);
        tree2.add_node(100);
        tree2.add_node(120);
        tree2.add_node(150);
        /*

              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
    public  function add_node($data)
    {
        $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();
    //  Added nodes
    $tree1->add_node(6);
    $tree1->add_node(9);
    $tree1->add_node(11);
    $tree1->add_node(3);
    $tree1->add_node(2);
    $tree1->add_node(45);
    $tree1->add_node(70);
    $tree1->add_node(4);
    $tree1->add_node(13);
    /*

              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
    $tree2->add_node(5);
    $tree2->add_node(9);
    $tree2->add_node(41);
    $tree2->add_node(8);
    $tree2->add_node(12);
    $tree2->add_node(50);
    $tree2->add_node(100);
    $tree2->add_node(120);
    $tree2->add_node(150);
    /*

          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
    add_node(data)
    {
        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();
    //  Added nodes
    tree1.add_node(6);
    tree1.add_node(9);
    tree1.add_node(11);
    tree1.add_node(3);
    tree1.add_node(2);
    tree1.add_node(45);
    tree1.add_node(70);
    tree1.add_node(4);
    tree1.add_node(13);
    /*

              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
    tree2.add_node(5);
    tree2.add_node(9);
    tree2.add_node(41);
    tree2.add_node(8);
    tree2.add_node(12);
    tree2.add_node(50);
    tree2.add_node(100);
    tree2.add_node(120);
    tree2.add_node(150);
    /*

          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
    def add_node(self, data) :
        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()
    #  Added nodes
    tree1.add_node(6)
    tree1.add_node(9)
    tree1.add_node(11)
    tree1.add_node(3)
    tree1.add_node(2)
    tree1.add_node(45)
    tree1.add_node(70)
    tree1.add_node(4)
    tree1.add_node(13)
    # 
    #                   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
    tree2.add_node(5)
    tree2.add_node(9)
    tree2.add_node(41)
    tree2.add_node(8)
    tree2.add_node(12)
    tree2.add_node(50)
    tree2.add_node(100)
    tree2.add_node(120)
    tree2.add_node(150)
    # 
    #               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_reader :data, :rank, :left, :right
    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_reader :root
    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
    def add_node(data) 
        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()
    #  Added nodes
    tree1.add_node(6)
    tree1.add_node(9)
    tree1.add_node(11)
    tree1.add_node(3)
    tree1.add_node(2)
    tree1.add_node(45)
    tree1.add_node(70)
    tree1.add_node(4)
    tree1.add_node(13)
    # 
    #                   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
    tree2.add_node(5)
    tree2.add_node(9)
    tree2.add_node(41)
    tree2.add_node(8)
    tree2.add_node(12)
    tree2.add_node(50)
    tree2.add_node(100)
    tree2.add_node(120)
    tree2.add_node(150)
    # 
    #               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();
        //  Added nodes
        tree1.add_node(6);
        tree1.add_node(9);
        tree1.add_node(11);
        tree1.add_node(3);
        tree1.add_node(2);
        tree1.add_node(45);
        tree1.add_node(70);
        tree1.add_node(4);
        tree1.add_node(13);
        /*

                  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
        tree2.add_node(5);
        tree2.add_node(9);
        tree2.add_node(41);
        tree2.add_node(8);
        tree2.add_node(12);
        tree2.add_node(50);
        tree2.add_node(100);
        tree2.add_node(120);
        tree2.add_node(150);
        /*

              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
    func add_node(_ data: Int)
    {
        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();
    //  Added nodes
    tree1.add_node(6);
    tree1.add_node(9);
    tree1.add_node(11);
    tree1.add_node(3);
    tree1.add_node(2);
    tree1.add_node(45);
    tree1.add_node(70);
    tree1.add_node(4);
    tree1.add_node(13);
    /*

             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
    tree2.add_node(5);
    tree2.add_node(9);
    tree2.add_node(41);
    tree2.add_node(8);
    tree2.add_node(12);
    tree2.add_node(50);
    tree2.add_node(100);
    tree2.add_node(120);
    tree2.add_node(150);
    /*

         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.

New Comment