Balance a Binary Tree

Introduction

This a description of an algorithm to balance an existing binary tree. There are many algorithms to do this. This is one of them.

Basically

  1. Get a list of values from somewhere
    • an existing tree
    • a list
    • a database
    • a file
    • a ...

  2. Sort the the list in ascending or descending order.
    If you don't sort the values, you will
    create an un-balanced tree.

  3. Pick the middle value and make it the root of the tree.

  4. You now have two sub-list (left and right)

  5. Loop
    1. Pick the middle value from a sub-list
    2. Add it to the tree starting at the root
    3. Do this for each sub-list
    4. keep doing this for each sub-sub-list
      until all of the nodes have been added

Pseudo Code - Create a Balanced Tree # ---- tree node definition ----------------------------------------- class Node: def __init__(self,value): self.value = value # node value self.parent = None # node parent self.left = None # left child self.right = None # right child self.depth = 0 # depth of node from tree root # ---- recursive function to add a node starting at the root -------- def add_node(node,parent): if node.value < parent.value: if parent.left == None: parent.left = node node.parent = parent node.depth = node_depth(node) return add_node(node,parent.left) return if parent.right == None: parent.right = node node.parent = parent node.depth = node_depth(node) return add_node(node,parent.right) return # ---- calculate a node's depth from the root node ------------------ def node_depth(node): dep = 0 ... return dep # ---- create a balanced tree --------------------------------------- def create_balanced_tree(old_root): # ---- recursive support function def balanced_tree_util(nodes,start,end,parent): if start > end: return None # ---- get middle node of the list mid = (start + end)//2 node = nodes[mid] # ---- construct/add to balanced tree # ---- a. fill in root node's value # ---- b. add a new node to the tree if parent.value is None: parent.value = node.value else: add_node(Node(node.value),parent) # ---- add left and right sub-trees to the node ... call create_balanced_tree_util on the ... left and right sub-lists return # ---- create a sorted list of node from the old tree ... # ---- create a root node for the balanced tree new_root = Node(None) # ---- create a new balanced tree n = len(nodes) balanced_tree_util(nodes,0,n-1,new_root) # ---- return the balanced tree return new_root # ---- main --------------------------------------------------------- tree = (a tree that needs balancing) new_tree = create_balanced_tree(tree)