Skip to content
  • Linkedin
  • Youtube
  • Pinterest
  • Home
  • Privacy Policy
  • About
  • Contact
Programmingoneonone

Programmingoneonone

Programmingoneonone is a website that publishes daily tutorials, methods, guides, and articles on IT, Education, and technology.

  • Home
  • Human Values
  • DSA
  • IoT Tutorials
  • Interview Questions and Answers
  • Toggle search form
Binary tree in data structure

Binary Tree in Data Structure

Posted on 30 May 202023 April 2023 By YASH PAL No Comments on 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 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.

Binary tree | properties | data structures and algorithms

What is a binary tree in Data structures?

It is a finite set of nodes that is either empty or consists of a distinguished node known as 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.

Binary tree | properties | data structures and algorithms

Properties of Binary Tree in Data Structure

Property first

In a binary tree, the maximum number of nodes on any level I is 2i

 where I >= 0

Property second

In a binary tree of height H, the maximum number of nodes possible is 2H – 1

Property third

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 which has nodes equal to their height are called skew trees.

Property fourth

For any binary tree with n nodes, the maximum height possible is n and the minimum height possible is [ log2(n+1)]

because the height can’t be more than n so 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.

Property fifth

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 so 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.

Property sixth

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

What is a 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.

Binary tree | properties | data structures and algorithms

What is an 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. and the special nodes are called external nodes and the original nodes are called internal nodes.

Binary tree | properties | data structures and algorithms

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 a sum of the path lengths of all internal nodes.

External path length: it’s a sum of the path lengths of all external nodes.

Property: 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.

What is a 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 node. then the height of a full binary tree is log2(n+1).

Binary tree | properties | data structures and algorithms

What is a 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 = [ log2(n+1)]

Binary tree | properties | data structures and algorithms

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())
Computer Science Tutorials, Data Structures Tutorials Tags:computer science, Data Structure

Post navigation

Previous Post: Tree in Data structure
Next Post: Array Representation of Binary Tree

Related Tutorials

vi editing commands VI Editing Commands For Linux Computer Science Tutorials
modes of vi editor VI Editor in Linux Computer Science Tutorials
environment and path setting in linux Environment and Path Setting in Linux Computer Science Tutorials
hard and synbolic links in linux Hard links and Symbolic links Computer Science Tutorials
changing file access permissions Changing File Access Permissions in Linux Computer Science Tutorials
access permissions in linux Access permissions in Linux Computer Science Tutorials

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick your Subject

  • Internet of Things
  • Data Structures/Algorithms
  • Interview Preparation
  • Human Values
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

  • Algorithms Tutorials
  • Basic Programming
  • C Programming Tutorials
  • C++ Tutorials
  • Compiler Design Tutorials
  • Computer Networks Tutorials
  • Computer Organization Tutorials
  • Computer Science Tutorials
  • Data Structures Tutorials
  • DBMS Tutorials
  • Developer Guide
  • Digital Communication
  • Digital Logic Tutorials
  • Internet of Things Tutorials
  • Internet Tutorials
  • Interview questions answers
  • Java Tutorials
  • Javascript Tutorials
  • Linux
  • Machine Learning Tutorials
  • Operating Systems Tutorials
  • Programming Tutorials
  • Projects
  • Tips&Tricks
  • Tools
  • VBScript Tutorials
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

Copyright © 2023 Programmingoneonone.

Powered by PressBook Blog WordPress theme