Given an inorder threaded binary tree and a node, how to find the parent of that particular node?

Question

We're given a binary tree with inorder threads. Meaning, if a node does not have a left child (right child), left threads (right threads) are linked from that node to its inorder predecessor (inorder successor).

Can you help me come up with pseudocode or algorithm that would find a node's parent? For example (see photo below), the given node is Q, the parent must be I. (We are supposed to make use of the given idea that the binary is inorder threaded)

TMI: I actually need this pseudocode/algorithm in creating another algorithm that would get the postorder successor of a binary tree.

Answer 1

From the picture it seems that:

• the head node is a special sentinel node that just serves as sentinel node for attaching the actual tree (which could be empty)
• nodes have two extra boolean flags to indicate whether they have a left/right child

Then the logic for finding the parent of a given node can be as follows:

• Find the right most node in the given node's subtree.
• Follow that node's right-link to an ancestor. We know that the original node is in the left subtree of this ancestor node.
• Check whether the left child of the ancestor is the original node. If so we found the parent.
• Go to the left child. We know that the original node must be on the right-side path below this node. Find it, and return the parent we had to visit before getting there.

Here is an implementation of that idea in JavaScript. This code snippet defines a Node class. It creates the tree given in the example. The Node class has an inorder iterator which we use to visit each node and then display its parent using the above algorithm:

class Node {
    constructor(value=null, left=null, right=null) {
        this.value = value;
        this.hasLeft = false;
        this.hasRight = false;
        this.left = left || this; // Default is self-reference
        this.right = right || this; // Default is self-reference
    }
    insertLeft(value) {
        this.hasLeft = true;
        this.left = new Node(value, this.left, this);
        return this.left;
    }
    insertRight(value) {
        this.hasRight = true;
        this.right = new Node(value, this, this.right);
        return this.right;
    }
    parent() {
        // Find rightmost node of subtree
        let node = this;
        while (node.hasRight) {
            node = node.right;
        }
        node = node.right; // go to ancestor
        // The this-node is in the left subtree of node.
        if (node.left === this) return node;
        node = node.left;
        while (node.right !== this) {
            node = node.right;
        }
        return node;
    }
    * inorder() {
        if (this.hasLeft) yield * this.left.inorder();
        if (this.right !== this) yield this; // When it is not the head
        if (this.hasRight) yield * this.right.inorder();
    }
}

// Create the example tree:
let head = new Node(); // Sentinel node (without data)
head.insertLeft("C").insertLeft("I").insertLeft("Q").insertRight("U").right.right
                    .insertRight("S").insertLeft("K").right
                                     .insertRight("R").insertLeft("O").right
                                                      .insertRight("T");

// Visit each node, display its value and that of its parent:
for (let node of head.inorder()) {
    console.log("parent of " + node.value + " is " + node.parent().value);
}