A linked binary tree suffers from wasting space in that all leaf nodes will have two null pointers.  Thus, if a tree has N nodes, it will have N + 1 null pointers.  We can remedy this situation by employing what are called "threads" in the normally null left or right links.  Threads are simply pointers to a node, but rather than point to a normal child node, threads are used to point to a node's (inorder, preorder, postorder) successor or predecessor.

We can thread a binary tree in whatever way makes sense for the application under consideration.  For example, if your job typically requires that a binary tree be traversed in the inorder sequence, we can thread the tree to enable us to do an inorder traversal.  Or, if your application dictates that both inorder and preorder traversals are commonly done, we can thread the tree to enable us to do both of these traversals.

The primary motivation for threading a tree to eliminate the need for recursion (or simulating recursion) in traversing a tree. Recursion is costly, it requires both time and stack space to save the local state before each call

In the tree below, we will put in the normally null left pointers, a thread to a node's inorder predecessor, and we will put in the normally null right pointers a thread to a node's inorder successor.  Threads will be represented as dashed lines and will be in red.

To achieve an inorder traversal of this tree, precede from a node to its inorder successor (Determined by 1 of 2 ways)
1) Look at node's right pointer: If it's a thread, the node pointed to is the node's inorder successor
2) Else (it's a normal pointer) Go to that node, and then follow left child pointers until you reach a left thread.

ALGORITHM General strategy is to precede one node to the right, then left as deep as possible into the tree.

P=A(ROOT)
REPEAT
    IF (P->TRLINK)  /* if P's right link is a thread */
        P=P->RLINK  /* go to the inorder successor */
    ELSE
        P=P->RLINK   /* else, go right, then left until you encounter a thread in left link */
        WHILE NOT P->TLLINK DO /*while llink not a thread */
            P=P->LLINK
        ENDWHILE
    ENDIF
/* P now points to its inorder successor */
/* check to see if P=TREEHDR; i.e., done */
    IF P NE TREEHDR
        PRINT P->INFO
    ENDIF
UNTIL P=TREEHDR

If we are to only traverse this tree in the forward inorder direction, the left threads (pointing to inorder predecessor) are really never used.  Thus, we could remove those threads and replace them by threads that would allow us to, say, perform a preorder traversal of the tree.  In that case, we would have a binary tree that permitted both preorder and inorder traversals non-recursively.

In the binary tree below, you will see that the normally null left links now contain a thread to a node's preorder successor, and the normally null right links contain a thread to a node's inorder successor.

Here is an algorithm to perform a preorder traversal of the tree above.

P=A(ROOT)
REPEAT
    go left (P=P->LLINK)
    If P not = ROOT
        PRINT P->INFO
    ENDIF
UNTIL ROOT

done to maximize the speed with which insertions & searches in a tree are handled.
Recall optimal search time in an ordered binary tree: log2 N+1
This is true only when tree is Full

• If data received wrong, could end up with = glorified linked lists
  

• Height balancing aims to keep the tree as full as possible while insertions are being processed, hence
  staying close to log2N+1
  

• Each node has another field which holds its balance factor   which is defined to be the difference
  between the height of the node's left subtree and the height of the node's right subtree.
  

• Height here is the number of nodes visited in traversing a branch that leads to a leaf node at the deepest level of the tree.

A tree is height balanced if  all its nodes have a BF of 1, 0, or -1.

Note that if a binary tree is Full, then it is also height-balanced but that the reverse does not hold true.

The algorithm to height balance a binary tree (as insertions are being processed) is non-trivial and development costs can rise in trying to implement it.   Addison-Velskii & Landis (1962) showed their method would guarantee a maximum branch length proportional to log2N, where N= # of nodes in tree.  In other words, insertion efficiency for a height-balanced tree will be roughly equivalent to that for a full tree.

Whether it's worth the added developmental costs is questionable. The answer depends on your applications.

GENERAL TREES (no birth control)

How best to represent?

• Fix the number of nodes as children: (wastes memory in null nodes)

• Allow variable size node? (need extra field in node defining number of children. Algorithms to handle are not elegant & more difficult)

The best representation is probably a binary representation.

Each node still has left and right pointers.

• Left pointer -> 1st child

• Right pointer -> Sibling

The root node of the general tree becomes the root node of the binary tree.

The preorder traversal of such a tree fixes on a node at one level and processes all its children before going to a node at same  level

Note that a preorder traversal of the binary representation of a general tree will recursively!

• process a parent node, then

• process its children from left to right

A post-order traversal works its way up from the leaf nodes of the tree, ensuring that no given node is processed until all nodes in the subtree below it have been processed.

We made use of this interesting fact as part of our recursive algorithm to print and then free nodes from a sorted binary tree.

One final note about algebraic expression trees.  For unary operators (such as negation, factorial, log, exponentiation, etc.) you will not that one of the two subtrees will be empty.  Some operators are written on the left (e.g., log(expr), cos(expr), -(expr))  and some operators are written on the right (e.g., n!)

If the operator is written on the left, treat the left subtree as empty,so the operands appear on the right side of the operator in the tree, just as they do in the expression.

If the operator is written on the right treat the right subtree as empty, so the operands will be in left subtree of operator.