PRESENTATION REPORT

FOR TOPIC
BINARY TREE

By:
Muhammad Mukarrum (02-134192-054)
Lavisha Chhatwani (02-134192-043)
Fatima Zafar (02-243212-010)

BSCS
Fall 2021

Submitted to:
Miss. Sameena Javaid
 Table of Contents
Abstract 3
Introduction 4
Common terms 5
Types of trees 6
Applications of Binary Trees 8

Operation of Binary Trees 9

Conclusion 10
References 11

2
 Abstract
It is computationally efficient to perform operations on balanced binary trees. A balanced
binary tree must meet the following criteria: The absolute difference between the heights of
the left and right subtrees is smaller than one at each node. Each node's left subtree is
represented by a balanced binary tree. In the real world, dealing with random values is nearly
difficult, while dealing with non-random values (such as sequential) leads to skew trees, which
is the worst-case scenario. As a result, to establish height balance, rotations are required. We
will discuss binary tree in more detail.

3
 Introduction

What is binary tree?

The number of children each node can have in a normal tree is unrestricted. In contrast, binary
trees can only have two children for each parent. A 'left' reference, a 'right' reference, and a
data element are all present in every node. The root node is the topmost node in the tree.
Parent nodes have children, and the child nodes have references to their parents. A leaf node is
a node that has no children. As shown in Figure below, each node inside a binary tree might
have 0, 1, or 2 offspring. An ordered pair of binary trees termed the left subtree and the right
subtree of that node form a binary tree, which can be external or internal.

Representation of a Binary Tree

A pointer to the topmost node in a tree is used to symbolize it. The value of root is NULL if the
tree is empty.
A Tree node contains following parts.
1. Data
2. Pointer to left child
3. Pointer to right child

4
Common Terms
 Root node: The topmost node in a tree
 Parent node: Every node in a tree (excluding the root) is connected to exactly one other
node by a directed edge. This node is referred to as a parent.
 Child node: When going away from the root, a child is a node that is directly related to
another node.
 Leaf/external node: Node with no children
 Internal node: Node having at least one child is referred to as an internal node.
 Depth of a node: The number of edges from the root to the node is the depth of a node.
 Height of a node: The number of edges from the node to the deepest leaf determines
the height of a node. The root's height is the tree's height.

The root node of the binary tree shown above is A. The tree comprises ten nodes, with
five internal (A,B,C,E,G) and five exterior (D,F,H,I,J) nodes. The tree stands at a height of
three meters. B is the father of D and E, while D and E are B's children.

Advantages of trees
Trees are so beneficial and widely used because they provide several significant benefits:

 The structural linkages in the data are shown in trees.

 Hierarchies are represented by trees.

5
  Insertion and searching are made easier with trees.
 Trees are an extremely versatile type of data because they allow you to shift subtrees
around with little effort.

Types Of Trees
There are several types of trees, some of them are listed below:
1. Rooted binary tree: A rooted binary tree contains a root node and at most two children
for each node.

2. Full Binary Tree: Binary Tree in its Complete Form If every node has 0 or 2 offspring, it is
called a full binary tree. A whole binary tree is shown in the examples below. A full
binary tree is a binary tree in which all nodes have two offspring except the leaf nodes.

 Nodes: the number of nodes, n, is at least 2h – 1 and at most 2h+1 – 1, where h is

the tree's height.
 leaf node: the number of leaf nodes l is equal to the number of internal nodes L + 1,
i.e., l = L+1.

6
3. Perfect binary tree: A Perfect Binary Tree is one in which all internal nodes have two
offspring, and all leaf nodes are on the same level. Perfect Binary Trees are
demonstrated in the following cases:
 The number of leaf nodes in a Perfect Binary Tree is equal to the number of internal
nodes plus one.
 I + 1 = L Where L denotes the number of leaf nodes, and I denotes the number of
internal nodes.
 There are 2h – 1 nodes in a Perfect Binary Tree of height h (where h is the longest
path from the root node to any leaf node in the tree, and the height of the root
node is 1).

4. Balanced binary tree: The height of a binary tree is balanced if it is O(Log n), where n is
the number of nodes. The AVL tree, for example, maintains O(Log n) height by ensuring
that the height difference between the left and right subtrees is no more than 1. Red-
Black trees keep their height constant by ensuring that the number of Black nodes on
each root-to-leaf path is the same and that no adjacent red nodes exist. Balanced Binary
Search trees provide good performance since they search, insert, and delete in O(log n)
time.

7
 5. Degenerate tree: A tree with one child for each internal node. Such trees perform
similarly to linked lists in terms of performance.

Applications of Binary Tree

There are many applications of binary tree and some of them are listed below:

 In Microsoft Excel and spreadsheets, the binary tree is the default data structure.
 The indexing of a Segmented Database is implemented using a Binary Tree.
 In both hardware and software systems, the Splay Tree (Binary Tree version) is utilized
to construct efficient caches.
 Back face culling, collision detection, Ray Tracing, and methods in rendering game
graphics all require Binary Space Partition Trees.
 Compilers like as GCC, AOCL, and others use Syntax Trees (Binary Trees with nodes as
operations) to construct arithmetic expressions.
 Priority Queue is implemented effectively using Binary Heap (Binary Tree form of Heap),
which is then used in the Heap Sort Algorithm.
 In Hash Map implementations, the Binary Search Tree is utilized to effectively search
entries and as a collision handling mechanism.
 To facilitate quick memory allocation, a Balanced Binary Search Tree is utilized to
represent memory.
 The Huffman Tree (Binary Tree variation) is utilized internally in the Huffman Encoding
and Decoding Greedy Algorithm for Data Compression.
 In Blockchain implementations and peer-to-peer (P2P) programmes that require
signatures, the Merkle Tree/ Hash Tree (Binary Tree version) is employed.
 Binary Tries (Tries with two children) are used to represent routing data that vacillates in
terms of traversal efficiency.
 Data is encoded using Morse code, which is represented using a Binary Tree.
 Using an arbitrary pseudorandom generator, the Gold Reich, Goldwasser, and Micali
(GGM) Tree (Binary Tree variation) is used to construct pseudorandom functions.
 The scapegoat tree (a self-balancing Binary Search Tree) is used to depict a defective
search process in Paul-Carole games.
 treasury (randomized Binary Search Tree)

8
Operations of Binary Tree
There are three operations of binary tree, which are as under.

 Insert: The very first insertion creates the tree. Afterwards, whenever an element is to
be inserted, first locate its proper location. Start searching from the root node, then if
the data is less than the key value, search for the empty location in the left subtree and
insert the data.

 Search: Whenever an element is to be searched, start searching from the root node,
then if the data is less than the key value, search for the element in the left subtree.
Otherwise, search for the element in the right subtree.

 Deletion: refers to the act of removal of a node from the binary tree , in deletion we
remove the element by replacing it with the rightmost element and delete the
rightmost leaf node when it is replaced.

Properties of binary tree

Till now we have discussed about introduction to binary trees and its applications, now we will
discuss its properties.
1. The maximum number of nodes in a binary tree at level 'l' is 2l. The number of nodes on
the path from the root to the node is called level (including root and node). The root's
level is zero. induction can be used to establish this. Number of nodes = 20 = 1 for root, l
= 0. Assume that on level 'l,' the maximum number of nodes is 2l. Because every node in
a Binary tree can only have two offspring, the following level will have twice as many
nodes, i.e., 2 * 2l.
2. In a binary tree of height 'h,' the maximum number of nodes is 2h – 1. The maximum
number of nodes on the root to leaf path determines a tree's height. A tree with a single
node is regarded to be one meter tall. The above-mentioned outcome can be deduced
from point 2. If all levels of a tree have maximum nodes, the tree is said to have
maximum nodes. In a binary tree of height h, the maximum number of nodes is 1 + 2 + 4
+... + 2h. This is a straightforward geometric series with h terms, and the sum is 2h– 1. In
some literature, the root's height is regarded as zero. The above expression becomes
2h+1 – 1 using this convention.
3. If we follow the convention of treating the height of a root node as 0, the formula for
the least feasible height becomes | Log2(N+1) | – 1.
9
 4. When all levels are fully filled, a Binary tree has the largest number of leaves (and the
smallest number of levels). If all the leaves are at level l, then the formula below holds
for the number of leaves L.
5. The number of leaf nodes in a binary tree with 0 or 2 children is always one more than
the number of nodes with two children.

Comparison of Binary Search Tree with Other Data Structures

 Binary Search Tree has better time complexity than linked list in case of searching an
element .
 For fast searching and in few insertion scenarios BST is preferred over linked list.
 In Binary Search the list is divided into two halves whereas in linear search each
element is scanned to search the target element.
 Binary Search works for sorted array while Linear search works for unsorted and sorted
array

Difference Between Binary Tree and Binary search Tree

While they both replicate a hierarchical tree structure with each node representing a value,
they are very different in terms of how they can be built and used. A Binary Tree follows one
basic rule: each parent node can have no more than two child nodes, but a Binary Search Tree
is simply a form of the binary tree that uses a relative order to organize the nodes in the tree.
Curly brackets are taken care of in most programming languages when opening and closing
braces. It mostly monitors it and throws an error if any closing brackets are missing.

Conclusion
One of the most often used trees in data structures is the binary tree. Each binary tree type has
its own set of characteristics. In applied computer science, these structures have certain
criteria. We hope you found this report on binary tree types, applications, and properties
useful.

10
REFERENCES
https://www.geeksforgeeks.org/binary-tree-set-1-introduction/
https://www.geeksforgeeks.org/binary-tree-set-2-properties/
https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/
https://www.studytonight.com/data-structures/introduction-to-binary-trees
https://owl.purdue.edu/owl/research_and_citation/ieee_style/ieee_general_format.html
http://www.differencebetween.net/technology/difference-between-binary-tree-and-binary-
search-tree/
https://iq.opengenus.org/applications-of-binary-tree/

11