Threaded binary tree.html

A threaded tree, with the special threading links shown by dashed arrows

A threaded binary tree may be defined as follows:

A binary tree is threaded by making all right child pointers, that would normally be null, point to the inorder successor of the node, and all left child pointers, that would normally be null, point to the inorder predecessor of the node."

(Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1989, p. 175. ISBN 978-0-201-16116-8.)

A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.

It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).

This is possible, because if a node (k) has a right child (m) then m's left pointer must be either a child, or a thread back to k. In the case of a left child, that left child must also have a left child or a thread back to k, and so we can follow m's left children until we find a thread, pointing back to k. The situation is similar for when m is the left child of k

In Python:

def parent(node):
    if node is node.tree.root:
        return None
    else:
        x = node
        y = node
        while True:
            if is_thread(y.right):
                p = y.right
                if p is None or p.left is not node:
                    p = x
                    while not is_thread(p.left):
                        p = p.left
                    p = p.left
                return p
            elif is_thread(x.left):
                p = x.left
                if p is None or p.left is not node:
                    p = y
                    while not is_thread(p.right):
                        p = p.right
                    p = p.right
                return p
            x = x.left
            y = y.right

Threaded binary tree.html

External links