GROUP 4

GROUP 4
DATA STRUCTURES &

ALGORITHMS
BINARY TREE
WHAT IS BINARY TREE DATA
STRUCTURE
A Binary Tree is a tree-type non-linear

data structure with maximun of two children for
each parent. Every node in a binary tree has a left
and right referrence along with the data element.
The node at the top of the hierarchy of
the tree is called the root node. The Nodes that
hold other sub-nodes are the parent nodes.
A parent node has two child nodes: the
left child and the right child. Hashing, routing Data
Terminologies Associated with Binary Trees and
Types of Binary Trees
Node: It represents a termination point in a tree.
Root: A tree’s topmost node.
Parent: Each node (apart from the root) in a tree that has at least one sub-
node of its own is called a parent node.
Child: A node that straightway came from a parent node when moving away
from the root is the child node.
Leaf Node: These are external nodes. They are the nodes that have no child.
Internal Node: As the name suggests, these are inner nodes with at least one
child.
Depth of a Tree: The number of edges from the tree’s node to the root is.
Height of a Tree: It is the number of edges from the node to the deepest leaf.
The tree height is also considered the root height.
Binary Tree Components
There are three binary tree
components. Every binary tree
node has these three
components associated with it. It
becomes an essential concept
for programmers to understand
these three binary tree
components:
1.Data element
2.Pointer to left subtree
3.Pointer to right subtree
Understanding Properties of
Binary Tree Or What Is Binary
Tree?
At every level of it, the maximum
number allowed for nodes stands at
2i.
The height of a binary tree stands

defined as the longest path emanating
from a root node to the tree’s leaf
node.
What Is Binary Tree– More Than The Binary Tree
Definition
Say a binary tree placed at a height equal to 3. In that case,
the highest number of nodes for this height 3 stands equal to 15,
that is, (1+2+4+8) = 15. In basic terms, the maximum node number
possible for this height h is (20 + 21 + 22+….2h) = 2h+1 -1.
Now, for the minimum node number that is possible at this
height h, it comes as equal to h+1.
If there are a minimum number of nodes, then the height of a
binary tree would stand aa maximum. On the other hand, when
there is a number of a node at its maximum, then the binary tree m
height will be minimum. If there exists around ‘n’ number nodes in a
binary tree, here is a calculation to clarify the binary tree definition.
The tree’s minimum
height is computed as:
n = 2h+1 -1
n+1 = 2h+1
Taking log for both sides now,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) – 1
The highest height will be computed
as:
n = h+1
h= n-1
5 TYPES OF BINARY TREE
1.Full Binary 2.Complete 3.Perfect

Tree. Binary Tree. Binary Tree.
4.Balanced 5.Degenerate
Binary Tree. Binary Tree.
In other words, a full binary tree is a
unique binary tree where every node
1.Full Binary Tree except the external node has two
children. When it holds a single child,
such a binary tree will not be a full
It is a special kind of a binary tree binary tree. Here, the quantity of leaf
that has either zero children or nodes is equal to the number of
two children. It means that all internal nodes plus one. The equation
is like L=I+1, where L is the number of
the nodes in that binary tree
leaf nodes, and I is the number of
should either have two child internal nodes.
nodes of its parent node or the
parent node is itself the leaf
node or the external node.
2. Complete Binary Tree
A complete binary tree is another specific type of binary tree
where all the tree levels are filled entirely with nodes, except
the lowest level of the tree. Also, in the last or the lowest
level of this binary tree, every node should possibly reside
on the left side. Here is the structure of a complete binary
tree:
3. Perfect Binary Tree
A binary tree is said to be ‘perfect’ if all the internal nodes
have strictly two children, and every external or leaf node is
at the same level or same depth within a tree. A perfect
binary tree having height ‘h’ has 2h – 1 node. Here is the
structure of a perfect binary tree:
4. Balanced Binary Tree
A binary tree is said to be ‘balanced’ if
the tree height is O(logN), where ‘N’
is the number of nodes. In a balanced
binary tree, the height of the left and
the right subtrees of each node
should vary by at most one. An AVL
Tree and a Red-Black Tree are some
common examples of data structure
that can generate a balanced binary
search tree. Here is an example of a
balanced binary tree:
5. Degenerate Binary Tree
A binary tree is said to be a
degenerate binary tree or
pathological binary tree if every
internal node has only a single
child. Such trees are similar to a
linked list performance-wise. Here
is an example of a degenerate
binary tree
The binary tree is one of the most
widely used trees in the data
structure. Each of the binary tree
types has its unique features.
These data structures have
Conclusion specific requirements in applied
computer science. We hope this
article about types of binary
trees was helpful. upGrad offers
various courses in data science,
machine learning, big data, and
more.
THANK YOU!

GROUP 4 - BINARY TREE

Uploaded by

Copyright:

Available Formats

GROUP 4 - BINARY TREE

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

GROUP 4 - BINARY TREE

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES &

A Binary Tree is a tree-type non-linear

The height of a binary tree stands

1.Full Binary 2.Complete 3.Perfect

You might also like