Binary Tree

A binary tree is a tree-like structure that has a root and in which each vertex has no more than two children. Each child of a vertex is called a left or right child.

Binary tree

Implementing a binary tree can be complex. The code below shows a simple implementation using a Tree Class. The first few methods have been implemented.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid

    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

There are three ways of traversing a binary tree: pre-order, in-order and post-order.

Pre-order In-order Post-order
Root Left sub-tree Left sub-tree
Left sub-tree Root Right sub-tree
Right sub-tree Right sub-tree Root

Exercises

  1. Implement the code given to start the binary tree implementation.
  2. Add the insertRightChild and insertLeftChild
  3. Now add the functions for printing the tree in pre-order order, in-order and post-order.

When you have tried the above exercises, you can download the whole program here.