Threaded Binary Tree - Types of Binary Trees

Types of Binary Trees

  1. Single Threaded: each node is threaded towards either the inorder predecessor or successor.
  2. Double threaded: each node is threaded towards both the inorder predecessor and successor.

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.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

Read more about this topic:  Threaded Binary Tree

Famous quotes containing the words types of, types and/or trees:

    “... there are two types of happiness and I have chosen that of the murderers. For I am happy. There was a time when I thought I had reached the limit of distress. Beyond that limit, there is a sterile and magnificent happiness.”
    —Albert Camus (1913–1960)

    “He’s one of those know-it-all types that, if you flatter the wig off him, he chatter like a goony bird at mating time.”
    —Michael Blankfort. Lewis Milestone. Johnson (Reginald Gardner)

    “Any walk through a park that runs between a double line of mangy trees and passes brazenly by the ladies’ toilet is invariably known as “Lover’s Lane.””
    —F. Scott Fitzgerald (1896–1940)