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 and/or trees:

    “The American man is a very simple and cheap mechanism. The American woman I find a complicated and expensive one. Contrasts of feminine types are possible. I am not absolutely sure that there is more than one American man.”
    —Henry Brooks Adams (1838–1918)

    “The trees persist, yeasty and sensuous,
    as thick as saints.”
    —Anne Sexton (1928–1974)