Threaded binary tree

From Wikipedia, the free encyclopedia

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, al beit slowly. This can be useful however where stack space is limited, or where a stack of parent pointers is unavailable.

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 psuedocode,

function getParent( node : pointer to a node )
begin
  if node == tree.root then
  begin
    return nil
  end
  x = node
  y = node
  while true do
  begin
    if IsThread(Y, Right) then
    begin
      p = y.right
      if (p == nil) or (p.left <> node) then
      begin
        p = x
        while not IsThread(p, Left) do
          p = p.left
        p = p.left
      end
      return p
    end
    if IsThread(Y, Left) then
    begin
      p = x.left
      if (p == nil) or (p.left <> node) then
      begin
        p = y
        while not IsThread(p, Right) do
          p = p.right
        p = p.right
      end
      return p
    end
    x = x.left
    y = y.right
  end