Binary tree vs Binary Search tree
First, we will understand the binary tree and binary search tree separately, and then
we will look at the differences between a binary tree and a binary search tree.
What is a Binary tree?
A Binary tree is a non-linear data structure in which a node can have either 0,
1 or maximum 2 nodes. Each node in a binary tree is represented either as a parent
node or a child node. There can be two children of the parent node, i.e., left
child and right child.
There is only one way to reach from one node to its next node in a binary tree.
A node in a binary tree has three fields:
Competitive questions on Structures in Hindi
Keep Watching
o Pointer to the left child: It stores the reference of the left-child node.
o Pointer to the right child: It stores the reference of the right-child node.
o Data element: The data element is the value of the data which is stored by the
node.
The binary tree can be represented as:
, In the above figure, we can observe that each node contains utmost 2 children. If any
node does not contain left or right child then the value of the pointer with respect to
that child would be NULL.
Basic terminologies used in a Binary tree are:
o Root node: The root node is the first or the topmost node in a binary tree.
o Parent node: When a node is connected to another node through edges, then
that node is known as a parent node. In a binary tree, parent node can have a
maximum of 2 children.
o Child node: If a node has its predecessor, then that node is known as a child
node.
o Leaf node: The node which does not contain any child known as a leaf node.
o Internal node: The node that has atleast 2 children known as an internal node.
o Depth of a node: The distance from the root node to the given node is known
as a depth of a node. We provide labels to all the nodes like root node is labeled
with 0 as it has no depth, children of the root nodes are labeled with 1, children
of the root child are labeled with 2.
o Height: The longest distance from the root node to the leaf node is the height
of the node.
In a binary tree, there is one tree known as a perfect binary tree. It is a tree in which
all the internal nodes must contain two nodes, and all the leaf nodes must be at the
same depth. In the case of a perfect binary tree, the total number of nodes exist in a
binary tree can be calculated by using the following equation:
n = 2m+1-1
where n is the number of nodes, m is the depth of a node.
What is a Binary Search tree?
A Binary search tree is a tree that follows some order to arrange the elements, whereas
the binary tree does not follow any order. In a Binary search tree, the value of the left
node must be smaller than the parent node, and the value of the right node must be
greater than the parent node.
Let's understand the concept of a binary search tree through examples.
First, we will understand the binary tree and binary search tree separately, and then
we will look at the differences between a binary tree and a binary search tree.
What is a Binary tree?
A Binary tree is a non-linear data structure in which a node can have either 0,
1 or maximum 2 nodes. Each node in a binary tree is represented either as a parent
node or a child node. There can be two children of the parent node, i.e., left
child and right child.
There is only one way to reach from one node to its next node in a binary tree.
A node in a binary tree has three fields:
Competitive questions on Structures in Hindi
Keep Watching
o Pointer to the left child: It stores the reference of the left-child node.
o Pointer to the right child: It stores the reference of the right-child node.
o Data element: The data element is the value of the data which is stored by the
node.
The binary tree can be represented as:
, In the above figure, we can observe that each node contains utmost 2 children. If any
node does not contain left or right child then the value of the pointer with respect to
that child would be NULL.
Basic terminologies used in a Binary tree are:
o Root node: The root node is the first or the topmost node in a binary tree.
o Parent node: When a node is connected to another node through edges, then
that node is known as a parent node. In a binary tree, parent node can have a
maximum of 2 children.
o Child node: If a node has its predecessor, then that node is known as a child
node.
o Leaf node: The node which does not contain any child known as a leaf node.
o Internal node: The node that has atleast 2 children known as an internal node.
o Depth of a node: The distance from the root node to the given node is known
as a depth of a node. We provide labels to all the nodes like root node is labeled
with 0 as it has no depth, children of the root nodes are labeled with 1, children
of the root child are labeled with 2.
o Height: The longest distance from the root node to the leaf node is the height
of the node.
In a binary tree, there is one tree known as a perfect binary tree. It is a tree in which
all the internal nodes must contain two nodes, and all the leaf nodes must be at the
same depth. In the case of a perfect binary tree, the total number of nodes exist in a
binary tree can be calculated by using the following equation:
n = 2m+1-1
where n is the number of nodes, m is the depth of a node.
What is a Binary Search tree?
A Binary search tree is a tree that follows some order to arrange the elements, whereas
the binary tree does not follow any order. In a Binary search tree, the value of the left
node must be smaller than the parent node, and the value of the right node must be
greater than the parent node.
Let's understand the concept of a binary search tree through examples.
