Binary Tree

Fig. A sample binary tree.

Trees are data structure which are of hierarchical order and every node, called a parent node, can have zero to many child node. A binary tree is a type of tree in which every parent node has at most two children.

Traversal of Binary Trees:

There are three ways to traverse a binary tree. We can also use them , with few modification, to traverse other type of trees. They are namely along with the parent-child configuration:

1) Inorder Traversing — — Left child/ Parent / Right child

IMPLEMENTATION — -

class Node:
    def __init__(self, value):
        self.left =None
        self.val = value
        self.right = None
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

2) Preorder Traversing — — Parent / Left child / Right child

IMPLEMENTATION — -

class Node:
    def __init__(self, value):
        self.left =None
        self.val = value
        self.right = None
def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

3) Postorder Traversing — — Left child / Right child / Parent

IMPLEMENTATION — -

class Node:
    def __init__(self, value):
        self.left =None
        self.val = value
        self.right = None
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

Time complexity in traversing is O(n).

The total number of nodes in a tree:

Below is a given script to find the total no. of nodes in a binary tree:

class Node:
    def __init__(self, value):
        self.left = None
        self.value = value
        self.right = None
def total_nodes(root):
    if(!root) :
        return 0
    else :
        return 1+total_nodes(root.left)+total_nodes(root.right)

Total number of possible trees:

Formula to find total number of unlabelled binary trees when “n” nodes are given:

Fig. Formula for unlabelled

Formula to find total number of labelled binary trees when “n” nodes are given:

Fig. Formula for labelled.