Binary Tree in Data Structure | DSA Tutorials

Binary Tree in Data Structure – A binary tree is a nonlinear data structure in which a node cannot have more than two child nodes. It means that if in a tree each node is either a leaf node or has one or two child nodes, then this tree is called a binary tree.

What is a Binary Tree?

A binary tree is a finite set of nodes that is either empty or consists of a distinguished node known as the root, and the remaining nodes are partitioned into two disjoint sets, T1 and T2, and both of them are binary trees. The T1 is called the left subtree, and T2 is called the right subtree.

Properties of a Binary Tree

1. In a binary tree, the maximum number of nodes on any level I is 2^l where I >= 0
2. In a binary tree of height H, the maximum number of nodes possible is 2^H – 1
3. In a binary tree of height H, the minimum number of nodes possible is H, because the minimum number of nodes possible at any level is 1 in a tree of height H, and there are H levels. and the tree that have nodes equal to their height are called skew trees.
4. For any binary tree with n nodes, the maximum height possible is n, and the minimum height possible is [ log₂(n+1)]. Because the height can’t be more than n, there should be at least one node at every level, and if the height is H, then the maximum number of nodes possible is 2H – 1.
5. In a non-empty binary tree, if n = number of nodes, e = number of edges, then e = n -1. Because every node has exactly one parent except the root node, and n-1 nodes have exactly one parent, there is only one edge between a parent and child. if the n = 1 and e = 0 then n = 1 so the property is true.
6. In a non-empty binary tree, if n0 = number of nodes with no child, n2 = number of nodes with 2 children then n0 = n2 + 1

Types of Binary Trees

1. Strictly binary tree
2. Extended binary tree
3. Full binary tree
4. Complete binary tree

Strictly binary tree

A binary tree in which each node is either a left node or has two children is called a strictly binary tree, and a strictly binary tree with n-leaf nodes has n-1 non-leaf nodes and a total of 2n – 1 nodes.

Extended Binary Tree

In a binary tree, if each empty subtree is replaced by a special node, then the resulting tree is called an extended binary tree or 2-tree. The special nodes are called external nodes, and the original nodes are called internal nodes.

• Path length: The number of edges traversed from that node to the root node is called the path length of a node.
• Internal path length: it is the sum of the path lengths of all internal nodes.
• External path length: it’s the sum of the path lengths of all external nodes.
• Property of Extended Binary Tree: In an extended binary tree, if E is the external path length, I is the internal path length, and n is the number of internal nodes, then E = I + 2n.

Full binary Tree

A binary tree in which each level has the maximum number of nodes is called a full binary tree. And if H is the height of a tree, then the binary tree will have 2H – 1 nodes. Then the height of a full binary tree is log₂(n+1).

Complete Binary Tree

In a complete binary tree, all levels have a maximum number of nodes except possibly the last level, and in the last level, the number of nodes ranges from 1 to 2H – 1, and all these nodes are towards the left. The height of a complete binary tree = [ log₂(n+1)]

Program to implement a binary tree using Python.

from collections import deque


class Node:
    def __init__(self, value):
        self.info = value
        self.lchild = None
        self.rchild = None

class BinaryTree:
    def __init__(self):
        self.root = None
    def is_empty(self):
        return self.root is None
    def display(self):
        self._display(self.root, 0)
        print()

    def _display(self,p,level):
        if p is None:
            return        self._display(p.rchild, level+1)
        print()

        for i in range(level):
            print(" ", end='')
        print(p.info)
        self._display(p.lchild, level+1)

    def preorder(self):
        self._preorder(self.root)
        print()

    def _preorder(self,p):
        if p is None:
            return        print(p.info, " ", end='')
        self._preorder(p.lchild)
        self._preorder(p.rchild)

    def inorder(self):
        self._inorder(self.root)
        print()

    def _inorder(self,p):
        if p is None:
            return        self._inorder(p.lchild)
        print(p.info," ", end='')
        self._inorder(p.rchild)

    def postorder(self):
        self._postorder(self.root)
        print()

    def _postorder(self,p):
        if p is None:
            return        self._postorder(p.lchild)
        self._postorder(p.rchild)
        print(p.info," ",end='')

    def level_order(self):
        if self.root is None:
            print("Tree is empty")
            return
        qu = deque()
        qu.append(self.root)

        while len(qu) != 0:
            p = qu.popleft()
            print(p.info + " ", end='')
            if p.lchild is not None:
                qu.append(p.lchild)
            if p.rchild is not None:
                qu.append(p.rchild)

    def height(self):
        return self._height(self.root)

    def _height(self,p):
        if p is None:
            return 0
        hL = self._height(p.lchild)
        hR = self._height(p.rchild)

        if hL > hR:
            return 1 + hL
        else:
            return 1 + hR

    def create_tree(self):
        self.root = Node('p')
        self.root.lchild = Node('Q')
        self.root.rchild = Node('R')
        self.root.lchild.lchild = Node('A')
        self.root.lchild.rchild = Node('B')
        self.root.rchild.lchild = Node('X')


##########################
bt = BinaryTree()

bt.create_tree()

bt.display()
print()

print("Preorder : ")
bt.preorder()
print("")

print("Inorder : ")
bt.inorder()
print()

print("Postorder : ")
bt.postorder()
print()

print("Level order : ")
bt.level_order()
print()

print("Height of tree is ", bt.height())

from collections import deque


class Node:
    def __init__(self, value):
        self.info = value
        self.lchild = None
        self.rchild = None

class BinaryTree:
    def __init__(self):
        self.root = None
    def is_empty(self):
        return self.root is None
    def display(self):
        self._display(self.root, 0)
        print()

    def _display(self,p,level):
        if p is None:
            return        self._display(p.rchild, level+1)
        print()

        for i in range(level):
            print(" ", end='')
        print(p.info)
        self._display(p.lchild, level+1)

    def preorder(self):
        self._preorder(self.root)
        print()

    def _preorder(self,p):
        if p is None:
            return        print(p.info, " ", end='')
        self._preorder(p.lchild)
        self._preorder(p.rchild)

    def inorder(self):
        self._inorder(self.root)
        print()

    def _inorder(self,p):
        if p is None:
            return        self._inorder(p.lchild)
        print(p.info," ", end='')
        self._inorder(p.rchild)

    def postorder(self):
        self._postorder(self.root)
        print()

    def _postorder(self,p):
        if p is None:
            return        self._postorder(p.lchild)
        self._postorder(p.rchild)
        print(p.info," ",end='')

    def level_order(self):
        if self.root is None:
            print("Tree is empty")
            return
        qu = deque()
        qu.append(self.root)

        while len(qu) != 0:
            p = qu.popleft()
            print(p.info + " ", end='')
            if p.lchild is not None:
                qu.append(p.lchild)
            if p.rchild is not None:
                qu.append(p.rchild)

    def height(self):
        return self._height(self.root)

    def _height(self,p):
        if p is None:
            return 0
        hL = self._height(p.lchild)
        hR = self._height(p.rchild)

        if hL > hR:
            return 1 + hL
        else:
            return 1 + hR

    def create_tree(self):
        self.root = Node('p')
        self.root.lchild = Node('Q')
        self.root.rchild = Node('R')
        self.root.lchild.lchild = Node('A')
        self.root.lchild.rchild = Node('B')
        self.root.rchild.lchild = Node('X')


##########################
bt = BinaryTree()

bt.create_tree()

bt.display()
print()

print("Preorder : ")
bt.preorder()
print("")

print("Inorder : ")
bt.inorder()
print()

print("Postorder : ")
bt.postorder()
print()

print("Level order : ")
bt.level_order()
print()

print("Height of tree is ", bt.height())