Description

After a tree is built, an attempt is made to to balance (re-order) the nodes to limit the depth of the tree. The re-order process start with the leaf nodes at the bottom of the tree and moves up, ending at the tree's root node. (See the description elsewhere in the documentation.)

Notes

• The pseudo code shows little error checking. See the code for the actual error checking.
• The functions return False if an error occurred and True if no error occurred.
• All nodes have a parent node except the root node. It is set to "None".
• The left subtree contains nodes less than the subtree's root node.
• The right subtree contains nodes greater than the subtree's root node.
• Duplicate nodes are not allowed
• Nodes
  • curnode = current working node
  • parnode = parent node of the current working node
  • pparnode = grand parent node of the current working node

Code

# ----------------------------------------------------------------------------------
# balance the tree
# ----------------------------------------------------------------------------------
function balance()
}
   # ---- is there a tree root node?
   # ---- interesting question - is this an error or not

   if tree.root == None { return True }

   # ---- skip over the root node and the level just below it
   # ---- if you want to know why, see the documentation/diagrams

   if tree.root.left != None
      if tree.root.left.left != None
         r = _balance(tree.root.left.left)
         if r != True { return False}
      if tree.root.left.right != None
         r = _balance(tree.root.left.right)
         if r != True { return False}      

   if tree.root.right != None
      if tree.root.right.left != None
         r = _balance(tree.root.right.left)
         if r != True { return False}
      if tree.root.right.right != None
         r = _balance(tree.root.right.right)
         if r != True { return False}

   return True
}

# ----------------------------------------------------------------------------------
# balance - helper function
# ----------------------------------------------------------------------------------
function _balance(curnode)                       # pass in the current node
{
   # ---- is there a current node?

   if curnode == None
      print('Oops, the current node is None')
      return False

   # ---- process the current node's left and right subtrees

   if curnode.right != None
      r = _balance(curnode.right)
      if r != True { return False }

   if curnode.left != None
      r = _balance(curnode.left)
      if r != True { return False }

   # ---- is the current node a leaf node?

   if curnode.left == None and curnode.right == None
      return True

   # ---- test current node's parent node

   parnode = curnode.parent

   if parnode == tree.root
      prnt('Oops, parnode is the tree root')
      return False    

   if parnode.left != curnode and parnode.right != curnode 
      print('Oops, parnode is not the parent of curnode')
      return False

   # --- test the current node's grand parent node

   pparnode = parnode.parent

   if pparnode.left != parnode and pparnode.right != parnode 
      print('Oops, pparent node is not the parent of parnode')
      return False

   # --- balance the current node?

   if curnode.data < parnode.data
      if curnode.right != None { return True }
      curnode.right = parnode
   elif curnode.data > paranode.data
      if curnode.left != None { return True }
      curnode.left = parnode
   elif curnode.data == parnode.data
      print('Oops, a duplicate node in the tree')
      return False
 
   if pparnode.left == parnode
      pparnode.left = curnode
   else
      pparnode.right = curnode

   curnode.parent = pparnode

   if parnode.left == curnode
      parnode.left = None
   else
      parnode.right = None

   parnode.parent = curnode

   return True
}