the left child of p—we can follow qs right children to a thread pointing ahead to p. In Python:def parent(node): if node is node.tree.root: return None x = node y = node while True: if is_thread(y): 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): p = x.left if p is None or p.right 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 Types Single threaded: each node is threaded towards either the in-order predecessor or successor (left or right). Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right). The array of in-order traversal Threads are reference to the predecessors and successors of the node according to an inorder traversal. In-order traversal of the threaded tree is A,B,C,D,E,F,G,H,I, the predecessor of E is D, the successor of E is F. Example Let's make the Threaded Binary tree out of a normal binary tree: The in-order traversal for the above tree is — D B A E C. So, the respective Threaded Binary tree will be -- Null links In an m-way threaded binary tree with n nodes, there are n×m − (n−1)' void links. References External links GNU libavl 2.0.2, Section on threaded binary search trees Articles with example Python (programming language) code Binary trees Search trees