ThreadedBinaryTree

Single Threaded Binary Search Tree

class Node {
    Node left;
    Node right;
    int data;
    boolean rightThread;

    public Node(int data) {
        this.data = data;
        rightThread = false;
    }
}

public class SingleThreadedBinaryTree {

    public static Node root;

    public void insert(Node root, int id) {
        Node newNode = new Node(id);
        Node current = root;
        Node parent = null;
        while (true) {
            parent = current;
            if (id < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    newNode.right = parent;
                    newNode.rightThread = true;
                    return;
                }
            } else {
                if (current.rightThread == false) {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        return;
                    }
                } else {
                    Node temp = current.right;
                    current.right = newNode;
                    newNode.right = temp;
                    current.rightThread = false;
                    newNode.rightThread = true;
                    return;
                }
            }
        }
    }

    public void print(Node root) {
        // first go to most left node
        Node current = leftMostNode(root);

        // now travel using right pointers
        while (current != null) {
            System.out.print(" " + current.data);
            // check if node has a right thread
            if (current.rightThread)
                current = current.right;
            else // else go to left most node in the right subtree
                current = leftMostNode(current.right);
        }
        System.out.println();
    }

    public Node leftMostNode(Node node) {
        if (node == null) {
            return null;
        } else {
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    }

    public static void main(String[] args) {
        root = new Node(100);
        SingleThreadedBinaryTree st = new SingleThreadedBinaryTree();
        st.insert(root, 50);
        st.insert(root, 25);
        st.insert(root, 7);
        st.insert(root, 20);
        st.insert(root, 75);
        st.insert(root, 99);

        st.print(root);
    }
}

Double Threaded Binary Search Tree

// Java program Insertion in Threaded Binary Search Tree. 
public class ThreadedBinaryTree {
    static class Node {
        Node left, right;
        int info;
        // True if left pointer points to predecessor
        // in Inorder Traversal
        boolean lthread;
        // True if right pointer points to predecessor
        // in Inorder Traversal
        boolean rthread;
    };

    // Insert a Node in Binary Threaded Tree
    static Node insert(Node root, int ikey) {
        // Searching for a Node with given value
        Node ptr = root;
        while (ptr != null) {
            // If key already exists, return
            if (ikey == (ptr.info)) {
                System.out.printf("Duplicate Key !\n");
                return root;
            }

            // Moving on left subtree.
            if (ikey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }

            // Moving on right subtree.
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }

        // Create a new node
        Node tmp = new Node();
        tmp.info = ikey;
        tmp.lthread = true;
        tmp.rthread = true;

        if (ptr == null) {
            root = tmp;
            tmp.left = null;
            tmp.right = null;
        } else if (ikey < (ptr.info)) {
            tmp.left = ptr.left;
            tmp.right = ptr;
            ptr.lthread = false;
            ptr.left = tmp;
        } else {
            tmp.left = ptr;
            tmp.right = ptr.right;
            ptr.rthread = false;
            ptr.right = tmp;
        }

        return root;
    }

    // Returns inorder successor using rthread
    static Node inorderSuccessor(Node ptr) {
        // If rthread is set, we can quickly find
        if (ptr.rthread == true)
            return ptr.right;

        // Else return leftmost child of right subtree
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
        return ptr;
    }

    // Printing the threaded tree
    static void inorder(Node root) {
        if (root == null)
            System.out.printf("Tree is empty");

        // Reach leftmost node
        Node ptr = root;
        while (ptr.lthread == false)
            ptr = ptr.left;

        // One by one print successors
        while (ptr != null) {
            System.out.printf("%d ", ptr.info);
            ptr = inorderSuccessor(ptr);
        }
    }

    // Driver Program
    public static void main(String[] args) {
        Node root = null;

        root = insert(root, 20);
        root = insert(root, 10);
        root = insert(root, 30);
        root = insert(root, 5);
        root = insert(root, 16);
        root = insert(root, 14);
        root = insert(root, 17);
        root = insert(root, 13);

        inorder(root);
        System.out.println();
    }
}