insert function for a preorder threaded binary search tree

Question

I'm trying to make a tree, in a way such that the left child of a terminal(leaf node) node.
link to see what tree should look like.

I've gotten an inorder version of the code i want, its a simple insert function that threads the tree ,but now my problem is changing this code into a preOrder insert.

This i can do, but my main problem is finding the preorder successor, which is all the way in a other sub tree, do any of you guys know a simple way to get the preorder successor?

//in-order insert
if (root == null) {                  // tree is empty
    root = newNode;
    return;
}
PreNode<T> p = root, prev = null;
    while (p != null) {              // find a place to insert newNode;
    prev = p;
    if (info.compareTo(p.info) < 0)
        p = p.left;
    else if (!p.hasThread)           // go to the right node only if it is
        p = p.right;                 // a descendant, not a successor;
    else break;                      // don't follow successor link;
}

if (info.compareTo(prev.info) < 0) { // if newNode is left child of
    prev.left  = newNode;            // its parent, the parent becomes
    newNode.hasThread = true;        // also its successor;
    newNode.right = prev;
}
else if (prev.hasThread) {           // if parent of the newNode
    newNode.hasThread = true;        // is not the right-most node,
    prev.hasThread = false;          // make parent's successor
    newNode.right = prev.right;      // newNode's successor,
    prev.right = newNode;
}
else prev.right = newNode;           // otherwise has no successor;

Gtamcn Gtamcn · Accepted Answer · 2014-03-22T12:09:33

This will work, assuming that there is a Node class which has right&left references to its children as well as a boolean variable ht which indicates if it has a thread or not.

public void insert(T info) {
        PreNode<T> newNode = new PreNode<T>(info);
        if (root == null) {
            root = newNode;
            return;
        }
        PreNode<T> curr = root, r = null, l = null;
        while (true) {
            if (info.compareTo(curr.info) < 0) {

                if (curr.right != null)
                    r = curr.right;

                if (curr.left == null || curr.ht) {
                    newNode.left = r;
                    curr.left = newNode;
                    curr.ht = false;
                    return;
                } else
                    curr = curr.left;
            } else {
                if (curr.left != null && !curr.ht)
                    l = curr.left;

                if (curr.right == null) {

                    if (curr.ht) {
                        newNode.left = curr.left;
                        newNode.ht = true;
                        curr.left = null;
                        curr.right = newNode;
                        curr.ht = false;
                        return;
                    } else
                        newNode.left = r;

                    curr.right = newNode;
                    curr.ht = false;

                    if (l != null) {
                        while (!l.ht) {
                            if (l.right != null)
                                l = l.right;
                            else
                                l = l.left;
                        }
                        l.left = newNode;
                        l.ht = true;
                        return;
                    }
                } else
                    curr = curr.right;
            }
        }
    }

insert function for a preorder threaded binary search tree

1 Answers