Binary Trees

MasterBlaster - VIVEK SAIL

IB requires the student to understand the following terms:

Binary Tree – A set of nodes that is either empty or partitioned into a root node and one or two subsets that are binary subtrees of the root. Each node has at most two children, the left child and the right child.

Binary Tree – Trees in which each node has at most two children. [IB]

Parent – [of node n] – The node directly above node n in the tree.

Parent - [node] - In a tree, any node which is not on the tip of a branch. [IB]

Left-child – A node directly below and to the left of the node n in a binary tree.

Left-child - In a tree, the node to the immediate left of a parent node. [IB]

Right-child – A node directly below and to the right of the node n in a binary tree.

Right-child - In a tree, the node to the immediate right of a parent node. [IB]

Subtrees – A tree that consists of a child (if any) of n and the child’s descendants.

Subtrees - A tree that is part of another tree. [IB]

A Binary Tree

In the above diagram,

1 is the parent of node 2 and 3.

2 is the left child of 1. 4 is the left child of 2. 6 is the left child of 3.

3 is the right child of 1. 5 is the right child of 2. 7 is the right child of 3.

2 is its children are subtree of 1. 3 and its children are a subtree of 1.

Other examples of binary trees:

All of the above diagrams are binary trees. Notice that no parent in a binary tree has more than two children.

Features and appropriate usage of binary trees.

Binary trees are position-oriented ADTs like stacks and queues. However, they are not linear like the latter two. This means, that you cannot reference items (nodes) in a binary tree by using a position number. The operations of a position-oriented ADT take the form of:

a. Insert a data item into the i^th position of a data collection.

b. Delete a data item from the i^th position of a data collection.

c. Ask a question about the data item in the i^th position of a data collection.

In a binary tree, there is no limit on the value of i while there is some restriction on the value of i when stacks and queues are used.

Binary trees are useful in modeling processes in which some experience or test with two possible outcomes (example: off or on, 0 or 1, false or true, down or up, higher or lower, greater or smaller) is performed repeatedly. The following binary tree is used to represent the possible outcomes of flipping a coin two times:

Similarly, binary trees could be used in coding problems such as in encoding and decoding messages transmitted in Morse code.

How branches operate:

To use memory space efficiently and to provide additional flexibility, binary trees are usually implemented as linked structures (like linked lists), in which each node has two pointers, one pointing to left child, the second pointing to right child (in both cases, if there is one).

A node in the binary tree

Points to left child Point to right child

If there are no children for the node, then the pointer just points to NULL. The children nodes have similar construction for themselves. In this way, the entire binary tree can be connected using pointers. Thus, an entire binary tree would look like:

Algorithms for Binary Trees

The algorithms required by IB are initialize, addition of nodes and traversal (pre-order, in-order and post-order). All the tree traversals have to be implemented recursively. The following are the algorithms (with their pseudocode):

A Binary Tree Node
A Binary Tree Class
Making The Tree
Adding To Left
Adding To Right
Pre-Order Traversal
In-Order Traversal
Post-Order Traversal

A Binary Tree Node
    In our example, we will store integers.

Pseudocode:
declare a pointer to the BinNode: BinNodePointer
declare a struct that will store the data item and the pointers: BinNode
   {
   declare an integer to store the data item: Item
   declare a pointer to the left child of this node: LeftPointer
   declare a pointer to the right child of this node: RightPointer
   }

Algorithm:
typedef struct BinNode* = BinNodePointer;
struct BinNode
{
   int Item;
   BinNodePointer Left;
   BinNodePointer Right;
};

A Binary Tree Class
    This is where most of the functions and root pointer will be in.

Pseudocode:
declare a class that will contain the required functions: BinaryTree
{
   public:
      declare a function to construct the tree: MakeTree
      declare a function to add a item to the left child: AddLeft
      declare a function to add a item to the right child: AddRight
      declare a function to traverse the tree (pre-order):PreOrder
      declare a function to traverse the tree (in-order):InOrder
      declare a function to traverse the tree (post-order):PostOrder

      declare a pointer to the root node of the tree: RootPointer

};

Algorithm:
class BinaryTree
{
   public:
      void MakeTree();
      void AddLeft(BinNodePointer current, int Data);
      void AddRight(BinNodePointer current, int Data);
      void PreOrder(BinNodePointer current);
      void InOrder(BinNodePointer current);
      void PostOrder(BinNodePointer current);

      BinNodePointer RootPointer;
};

Making The Tree

Pseudocode:
void MakeTree()
{
   declare an integer to store the user inputed data value: UserData
   while (the user does not input 9999)
      {
      ask the user to enter a data value
      get the data value
      if the data value is equal to 9999
         then exit the loop
      else
         {
         if this is the first entry
            {
            make a new node: Leaf
            make Leaf's Item = data value
            make this Leaf the root
            make the left pointer and right pointer equal to NULL
            }
         else
            {
            if the data value is greater than root pointer's value
               AddRight(RootPointer->Right,UserData);
            if the data value is smaller than root pointer's value
               AddLeft(RootPointer->Left,UserData);
            }
         }
      }
}

Algorithm:
void MakeTree()
{
   int UserData=0;
   while (UserData!=9999)
      {
      cout << "Enter Data: ";
      cin >> UserData;
      if (UserData==9999)
         break;
      else
         {
         if (RootPointer==NULL)
            {
            Leaf = new BinNode;
            Leaf.Item = UserData;
            Leaf.Left = NULL;
            Leaf.Right = NULL;
            }
         else
            {
            if (UserData > RootPointer.Item)
               AddRight(RootPointer->Right,UserData);
            if (UserData < RootPointer.Item)
               AddLeft(RootPointer->Left,UserData);
            }
         }
      }
}

Adding to Left
The following code is done recursively.

Pseudocode:
void AddLeft(BinNodePointer current, int Data)
{
   if no node exist
      {
      make a new node: Leaf
      make its data item equal to Data
      make its right pointer and left pointer NULL
      }
   else
      {
      if the Data value is greater than the data item in the current node
         call AddRight and pass in the pointer to the right child and the data value
      else if the data value is smaller than the data item in the current node
         call AddLeft and pass in the pointer to the left child and the data value
      }
}

Algorithm:
void AddLeft(BinNodePointer current, int Data)
{
   if (current==NULL)
      {
      Leaf = new BinNode;
      Leaf.Item = Data;
      Leaf.Right = NULL;
      Leaf.Left = NULL;
      }
   else
      {
      if (Data > current.Item)
         AddRight(current->Right,Data);
      else if (Data < current.Item)
         AddLeft(current->Left,Data);
      }
}

Adding to Right
The following code is done recursively.

Pseudocode:
void AddRight(BinNodePointer current, int Data)
{
   if no node exist
      {
      make a new node: Leaf
      make its data item equal to Data
      make its right pointer and left pointer NULL
      }
   else
      {
      if the data value is greater than the data item in the current node
         call AddRight and pass in the pointer to the right child and the data value
      else if the data value is smaller than the data item in the current node
         call AddLeft and pass in the pointer to the left child and the data value
      }
}

Algorithm:
void AddRight(BinNodePointer current, int Data)
{
   if (current==NULL)
      {
      Leaf = new BinNode;
      Leaf.Item = Data;
      Leaf.Right = NULL;
      Leaf.Left = NULL;
      }
   else
      {
      if (Data > current.Item)
         AddRight(current->Right,Data);
      else if (Data < current.Item)
         AddLeft(current->Left,Data);
      }
}

Pre-Order Traversal
This is only 1 of the possible ways to traverse a tree. The basic procedure involved in a pre-order traversal is:
                                                    Read the Data
                                                    Move to the left child
                                                    Move to the right child

Pseudocode:
void PreOrder(BinNodePointer current)
{
   if no node exists,
      return back to the previous call of the function
   display the integer stored in the data item
   call the function PreOrder and pass in the pointer to the left child
   call the function PreOrder and pass in the pointer to the right child
}

Algorithm:
void PreOrder(BinNodePointer current)
{
   if (current==NULL)
      return;
   cout << current.Item;
   PreOrder(current->Left);
   PreOrder(current->Right);
}

In-Order Traversal
This is only 1 of the possible ways to traverse a tree. The basic procedure involved in an in-order traversal is:
                                                                Move to the left child
                                                                Read the Data
                                                                Move to the right child

Pseudocode:
void InOrder(BinNodePointer current)
{
   if no node exists,
      return back to the previous call of the function
   call the function PreOrder and pass in the pointer to the left child
   display the integer stored in the data item
   call the function PreOrder and pass in the pointer to the right child
}

Algorithm:
void InOrder(BinNodePointer current)
{
   if (current==NULL)
      return;
   PreOrder(current->Left);
   cout << current.Item;
   PreOrder(current->Right);
}

Post-Order Traversal
This is only 1 of the possible ways to traverse a tree. The basic procedure involved in a post-order traversal is:
                                                                    Move to the left child
                                                                    Move to the right child
                                                                    Read the Data

Pseudocode:
void InOrder(BinNodePointer current)
{
   if no node exists,
      return back to the previous call of the function
   call the function PreOrder and pass in the pointer to the left child
   call the function PreOrder and pass in the pointer to the right child
   display the integer stored in the data item
}

Algorithm:
void InOrder(BinNodePointer current)
{
   if (current==NULL)
      return;
   PreOrder(current->Left);
   PreOrder(current->Right);
   cout << current.Item;
}