Module 4
TREES-BINARY TREES
Binary Tree is a non-linear and hierarchical data structure where each
node has at most two children referred to as the left child and the
right child. The topmost node in a binary tree is called the root, and
the bottom-most nodes(having no children) are called leaves.
Representation of Binary Tree
Each node in a Binary Tree has three parts:
Data
Pointer to the left child
Pointer to the right child
Terminologies in Binary Tree
Parent Node: A node that is the direct ancestor of a node(its
child node).
Child Node: A node that is the direct descendant of another
node (its parent).
Ancestors of a node: All nodes on the path from the root to that
node (including the node itself).
Descendants of a node: All nodes that lie in the subtree rooted
at that node (including the node itself).
Subtree of a node: A tree consisting of that node as root and all
its descendants.
Edge: The link/connection between a parent node and its child
node.
Path in a binary tree: A sequence of nodes connected by edges
from one node to another.
Leaf Node: A node that does not have any children or both
children are null.
Internal Node: A node that has at least one child.
Depth/Level of a Node: The number of edges in the path from
root to that node. The depth/level of the root node is zero.
Height of a Binary Tree: The number of edges on the longest
path from root to a leaf.
Creating a Binary Tree
In this example, we will explore how to create a Binary Tree with four
nodes 2, 3, 4, 5.
#include <stdio.h>
#include <stdlib.h>
struct Node // Node structure
{
int data;
struct Node *left;
struct Node *right;
};
struct Node* createNode(int d)
{
struct Node* newNode =
(struct Node*)malloc(sizeof(struct Node));
newNode->data = d;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main()
{
// Initialize and allocate memory for tree nodes
struct Node* firstNode = createNode(2);
struct Node* secondNode = createNode(3);
struct Node* thirdNode = createNode(4);
struct Node* fourthNode = createNode(5);
// Connect binary tree nodes
firstNode->left = secondNode;
firstNode->right = thirdNode;
secondNode->left = fourthNode;
return 0;
}
Applications of Binary Tree
Binary Tree can be used to represent hierarchical data.
Huffman Coding trees are used in data compression algorithms.
Useful for indexing segmented at the database is useful in
storing cache in the system,
Binary trees can be used to implement decision trees, a type of
machine learning algorithm used for classification and
regression analysis.
Binary Tree Representation
There are two primary ways to represent binary trees:
1. Linked Node Representation i.e(Linked List)
2. Array Representation
NOTE: Only Learn Array Representation
you have only second type
2. Array Representation
Array Representation is another way to represent binary trees,
especially useful when the tree is complete. In this method:
The tree is stored in an array.
Consider the below complete binary tree
Level
1
Level
2
Level
3
Representing above binary tree in an array as shown in the below
elements 10 9 5 8 4 2 3
0 1 2 3 4 5 6 index
Example 2: Consider the below binary tree
Case 1: If the index is starting from 0 index
Formula to find the left node and right node of a tree in array
representation.
Case 2: if the index is starting from 1
Formula to find the left node and right node of a tree in array
representation.
In Example 2: Binary tree if not full complete binary tree .
make it complete binary tree add the nodes at the last level as shown
in the below figure
U can find the parent of Node H by using any case(case1 or case2)
Answer is E (apply the formula)
Advantages:
Easy to navigate parent and child nodes using index
calculations, which is fast
Easier to implement, especially for complete binary trees.
Disadvantages:
You have to set a size in advance, which can lead to wasted
space.
If the tree is not complete binary tree then then many slots in the
array might be empty, this will result in wasting memory
Not as flexible as linked representations for dynamic trees.
Video Link: [Link]
Types of Binary Trees
1 Full Binary Tree
A Full Binary Tree is a type of binary tree where every node has
either zero or two children. In other words, no node has only one
child.
2 Complete Binary Tree
In a complete binary tree, all levels are completely filled with nodes,
except possibly for the last level. On the last level, nodes are filled
from left to right.
3 Perfect Binary Tree
A perfect binary tree is a special case in which it is both a
full and complete binary tree. It's the most symmetrical type of binary
tree, where all internal nodes have two children, and all leaf nodes are
at the same level (depth).
Interesting Properties of Perfect Binary Trees:
The total number of nodes doubles as we move down each level.
You can see in the image that the first level contains one node,
the second level contains two nodes, and the third level contains
four nodes. If we had another level, it would contain eight
nodes, and so on. In other words, this means that the height of
the tree grows logarithmically.
The number of nodes at the last level equals the sum of nodes at
all other levels plus one.
4 Balanced Binary Tree
A balanced binary tree (or height-balanced binary tree) is a binary tree
where the height of the left and right subtrees of any node differs by at
most one.
In the image below, the height of the left side from the root node is
two, and the height of the right side is one, so the tree is balanced as
the heights don't differ by more than one.
If we added another node on the left side, the tree would become
imbalanced as the height of the left side, looking from the root node,
would become three, and the height of the right side would still be
one.
Threaded Binary Trees
Threaded binary tree is a binary tree where in address field
will either hold the address of the successor node/the
predecessor node in the address field.
Step 1: take binary tree
Consider the below example of binary tree
Nodes are 10,5,2,7,15,9
Step 2: represent this binary tree into an list representation, as
shown in the below figure
The leaf nodes are 7,15,9 and the address of these nodes is
NULL (i.e /)
No of nodes =n=6
No of NULL addresses = n+1= 7
In the above representation of threded binary tree rather
than soring address field as NULL we store the address
of the another node.
Note:
1. Left threaded binary trees( i.e in left address) we
can store the address of predecessor node (previous
node).
2. Right threaded binary trees( i.e in right address) we
can store the address of successor node (next node)
Step 2: Find the in-order traversal for the above represented
binary tree
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
In left threaded binary tree
Now check the predecessor of 7 .
here in the in-order traversal there is no previous node is there
for node 7. {have to check always in In-Order traversal
is(left-root-right) : 7,5,15,10,2,9}
Now check the predecessor of 15 is 5 .
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
predecessor of 9 is 2.
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
predecessor of 2 is 10.
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
Node 7 does not have predecessor then add head node to
the tree and the head of left is always pointing to the root
node and head of right is pointing to itself
Node 7 left address is now pointing to header node
In RIGHT threaded binary tree
3 Null addresses are there
node 7 -successor is 5
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
node 15 -successor is
In-Order traversal is(left-root-right) : 7,5,15,10,2,9
node 9 -successor is not there it will point to head node.
As shown in the below figure
fully in-order threaded binary tree is