BINARY TREE SORT - Relies on the ordering property of binary trees.

String of numbers: 23, 17, 65, 3, 15, 14, 35, 23

1) Construct a binary search tree
* make 1st number the Root
* insert new node X to left of current node Y, if X<Y
* insert new node X to right of current node Y, if X>=Y

2) To print numbers in sorted order do an inorder traversal :

3 14 15 17 23 23 35 65

Note:  This is a stable sorting algorithm. Records with equal keys (if duplicate keys are permitted) maintain their relative position within the sort.

To get rid of the tree (i.e., an algorithm to move nodes to an array in sorted order while freeing the nodes.)  This algorithm does a blend of inorder & postorder traversal

1.) Traverse Left
2.) Move tree node to array
3.) Traverse Right
4.) Free the Root -> lets us return nodes back to the stack or back to O/S in the order in which they appear in the tree.

An algorithm to insert a node into an orderd binary tree (duplicate keys not permitted)

INSERT(THDR,NODE)
T=A(THDR)
P=T->LINK
IF P=/\
  T->LINK=NODE
ELSE
  DOWHILE (P NE /\) AND (P->KEY NE NODE->KEY)
    IF (NODE->KEY GE P->KEY)
      Q=P->RLINK
      IF Q=/\
        P->RLINK=NODE
      ENDIF
    ELSE
      Q=P->LLINK
      IF Q=/\
        P->LLINK=NODE
      ENDIF
  ENDIF
  P=Q
  ENDDO
  IF (P NE /\)
    Duplicate Key
  ELSE
    PRINT NODE INFO; NULL OUT L & R LINKS
ENDIF

** Think about a recursive algorithm to insert nodes into an ordered Binary Tree!

Search for a Key in an Ordered Binary Tree - Recursive

Search(Node, Target, Loc)
/* Node - ptr to a node in the tree
Target - key to search for
Loc - ptr to found node or null */

If Node = null
  loc - null
else
  if node-> key = target
    loc = node
  else
    if target < node->key
      Search(node->llink, target, loc)
    else
      Search(node->rlink, target,loc)
    endif
  endif
endif
return (loc)

** Think about a non-recursive algorithm to do a search!

Given any node, we know
all nodes < that node on left subtree
all nodes >= that node on right subtree

There are two basic strategies for which node we should use to replace a deleted node with in the tree:
    its inorder predecessor (largest element in left subtree of node to delete)
    its inorder successor (smallest element in right subtree of node to delete)

Best to adopt one of these strategies and stick with it. In some cases, however, the node to replace the deleted node will be neither inorder predecessor or successor.

Ptrs: L - will address parent of node to delete
P - will address node to delete
Q - will address the inorder successor of node P
F and R - used to chase down left link of P's right child
Integer: DeltKey - contains key of node to delete

L = A(TreeHdr)      L has address of tree header
Found = False        initialize boolean variable
Do While (L-> Link != null and not Found)
  P = L-> Link
  if P-> Key = DeltKey
    Found = true
  else if P-> Key < DeltKey
    L = A(P->Rlink)*
    else
      L = A(P->Llink)*
    endif
  endif
Enddo

* Note that pointer L is being assigned the address of the link field of node P; i.e., a register is LAed to the beginning of the link field. In this way, no determination has to be made regarding whether we have gone left or right. The lag pointer will always be pointing to the correct link field. Thus, at the top of the loop, P is assigned the address of where pointer L is. We do not have to specify Llink or Rlink.

if L-> Link = null
  node not in tree
else
  Q = P->Rlink                       point to delete node's right subtree
  if Q = null                            if no right subtree, assign delete node's
    L->Link = P->Llink           left tree as replacement node
  else                                     delete node does have a right subtree
    F = A(P->Rlink)               F points to Rlink field of node P
    continue = true                  set boolean control variable
    Do While(continue)           find smallest node in right subtree
      Q = F->Link                   when ptr R is null, Q will be pointing
      R = Q->Llink                  to the inorder successor of the node to
      if R = null                       delete
        continue = false
      else
        F = A(Q->Llink)
      endif
    Enddo
    R = Q->Rlink                    get right child of repl node (if any)
    F->Link = R                      assign as new left child to lag ptr
    Q->Llink = P->Llink        get delete node's left tree
    Q->Rlink = p->Rlink       get delete node's right tree
    L=>Link = Q                   point parent of delete node to new child
  endif
endif
Retrun (P)

Assume we have a sorted array | 1 | 2 | 3 | 4 | 5 | 6 | ....|

Here is a recursive algorithm to build an ordered balanced Binary tree from the entries in the array.

BLD(FIRST,LAST)
/* FIRST & LAST always point to slots in the array. They are initially set to the first and last entries of the entire array */

IF FIRST > LAST
  RETURN NULL POINTER
ELSE
  IF FIRST=LAST
    getmain for P's node
    move in data; set RLINK & LLINK = null
    RETURN(P)
  ELSE
    MID=[(F+L)/2]   round down in division
    getmain node: P->node
    move data to P
    BLD(FIRST,MID-1)
    P->LL=RET.VALUE from BLD
    BLD(MID+1,LAST)
    P->RL=RET.VALUE from BLD
    RETURN(P)
  ENDIF
ENDIF