Unit Vi Trees

UNIT VI -TREES
LECTURER
ER.MOHANAPRIYA
What is a Tree in Data structure?
• A tree is a hierarchical data structure that contains a collection of
nodes connected via edges so that each node has a value and a list of
pointers to other nodes. (Similar to how parents have the reference to
their children in a family tree)
Following are the key points of a tree data structure:
• Trees are specialized to represent a hierarchy of data
• Trees can contain any type of data be it strings or numbers
Basic terms of tree data structure
Root node
• The topmost node in the tree hierarchy is known as the root node.
• In other words, it's the origin point of the tree that doesn't have any parent node.
Child node
• The descendant of any node is said to be a child node.
Parent node
• If the node has a descendant i.e. a sub-node, it's called the parent of that sub-node.
Siblings
• Just like a family tree, nodes having the same parent node are called siblings
Leaf node
• It's the bottom-most node in the tree that doesn't have any child node. They are also
called external nodes. The "end" of a tree branch is normally where the leaf nodes are
located.
Internal node
• A node having at least one child node is known as an internal node. Internal nodes in a
tree structure are often located "between" other nodes.
Ancestor Node
• Any node that lies between the root and the current node is considered to be an
ancestor node. You may think of ancestor nodes as "parents, grandparents,
Descendant
• A descendant is any child, grandchild, great-grandchild, etc. of the
current node. Any node in the tree structure that is "below" the
current node is referred to as a descendent.
Edges
• The link between any two nodes is called an edge.
What is a Binary Tree
• A binary tree is a a collection of nodes that consists of the root and
other subsets to the root points, which are called the left and right
subtrees.
• Every parent node on a binary tree can have up to two child nodes
(roots of the two subtrees); any more children and it becomes a
general tree.
• A node that has no children is called a leaf node.

A Few Terms Regarding Binary Trees
B C
D E F
A is the root
B and C are A’s children
A is B’s parent
B & C are the root of two subtrees G
D, E, and G are leaves
This is NOT A Binary Tree
B C
D E F G H
This is a general tree because C has three child nodes

This is NOT A Binary Tree
B C
D E F G
This is a graph H
because A, B, E, H, F and C
form a circuit
SEARCH ALGORITHM
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
Tree Traversal
• In linear data structures like arrays, stacks, etc. there's only one way
to traverse the data.
• But, a hierarchical data structure like a tree can have different ways of
traversal.
• In order to traverse a tree, we need to read all the nodes in the left
subtree, the root node, and all the nodes in the right subtree.
Tree Traversal
• There are three common ways to traverse a tree:

• Preorder: Visit the root, traverse the left subtree (preorder) and then traverse
the right subtree (preorder)
• Postorder: Traverse the left subtree (postorder), traverse the right subtree
(postorder) and then visit the root.
• Inorder: Traverse the left subtree (in order), visit the root and the traverse the
right subtree (in order).
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECFG
Postorder: DEBGFCA G
In Order: DBEAFGC
A
B C
D E F
Preorder: A
(visit each node as your reach it) G
A
B C
D E F
Preorder: AB
A
B C
D E F
Preorder: ABD
A
B C
D E F
Preorder: ABDE
A
B C
D E F
Preorder: ABDEC
A
B C
D E F
Preorder: ABDECF
A
B C
D E F
Preorder: ABDECFG
A
B C
D E F
Postorder:
G
A
B C
D E F
Postorder:
G
A
B C
D E F
Postorder: D
G
A
B C
D E F
Postorder: DE
G
A
B C
D E F
Postorder: DEB
G
A
B C
D E F
Postorder: DEB
G
A
B C
D E F
Postorder: DEB
G
A
B C
D E F
Postorder: DEBG
G
A
B C
D E F
Postorder: DEBGF
G
A
B C
D E F
Postorder: DEBGFC
G
A
B C
D E F
Postorder: DEBGFCA
G
A
B C
D E F
G
In Order:
A
B C
D E F
G
In Order:
A
B C
D E F
G
In Order: D
A
B C
D E F
G
In Order: DB
A
B C
D E F
G
In Order: DBE
A
B C
D E F
G
In Order: DBEA
A
B C
D E F
G
In Order: DBEA
A
B C
D E F
G
In Order: DBEAF
A
B C
D E F
G
In Order: DBEAFG
A
B C
D E F
G
In Order: DBEAFGC
A
B C
D E F
Preorder: ABDECFG
Postorder: DEBGFCA G
In Order: DBEAFGC
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIECG
Postorder: HIFDEBGCA
H I In Order: DHFIBEACG
EXPRESSION TREE
Basic operations
Here are a few basic operations you can perform on a tree:
Insertion:
• Insertion can be done in multiple ways depending on the location
where the element is to be inserted.
• We can insert the new element at the rightmost or the leftmost
vacant position
• Or just insert the element in the first vacant position we find when we
traverse a tree
Let's determine the vacant place with In-order traversal.
Parameters: root, new_node
• Check the root if it's null, i.e., if it's an empty tree. If yes, return the new_node
as root.
• If it’s not, start the in order traversal of the tree
• Check for the existence of the left child. If it doesn't exist, the new _node will
be made the left child, or else we'll proceed with the in order traversal to find
the vacant spot
• Check for the existence of the right child. If it doesn't exist, we'll make the right
child as the new_node or else we'll continue with the in order traversal of the
right child.
PSEUDOCODE FOR INSERTION
TreeNode insert_node _inorder(TreeNode root, TreeNode new_node)
{
if ( root == NULL )
return new_node
if ( root.left == NULL )
root.left = new_node
else
root.left = insert_node_inorder(root.left, new_node)
if ( root.right == NULL
root.right = new_node
else
root.right = insert_node_inorder(root.right, new_node)
return root
}
Searching
• It's a simple process in a binary tree. We just need to check if the

current node's value matches the required value and keep
repeating the same process to the left and right subtrees using a
recursive algorithm until we find the match.
PSEUDOCODE FOR SEARCHING
bool search(TreeNode root, int item)
{
if ( root == NULL )
return 0
if ( root.val == item )
return 1
if ( search(root.left, item) == 1 )
return 1
else if ( search(root.right, item) == 1 )
return 1
else
return 0
}
Deletion
• It's a bit tricky process when it comes to the tree data structure.
There are a few complications that come with deleting a node
such as-
• If we delete a node, what happens to the left child and the right
child?
• What if the node to be deleted is itself a leaf node?
• Simplifying this - the purpose is to accept the root node of the tree
and value item and return the root of the modified tree after we have
deleted the node.
• Firstly, we'll check if the tree is empty i.e. the root is NULL. If yes, we'll
simply return the root.
• We'll then search for an item in the left and the right subtree and
recurse if found.
• If we don't find the item in both the subtrees, either the value is not
in the tree or root.val == item.
• Now we need to delete the root node of the tree. It has three
possible cases.
CASE 1 - The node to be deleted is a leaf node.
• In this case, we'll simply delete the root and free the allocated
space.
CASE 2 - It has only one child.
• We can't delete the root directly as there's a child node

attached to it. So, we'll replace the root with the child node.
CASE 3 - It has two children nodes.
• In this case, we'll keep replacing the node to be deleted
with its in-order successor recursively until it's placed on
the leftmost leaf node. Then, we'll replace the node with
NULL and delete the allocated space.
• In other words, we'll replace the node to be deleted with
the leftmost node of the tree and then delete the new
leaf node.
• This way, there's always a root at the top and the tree
shrinks from the bottom.
PSEUDOCODE FOR DELETION
TreeNode delete_element(TreeNode root, int item)
{
if ( root == NULL )
return root
if ( search(root.left, item) == True )
root.left = delete_element(root.left, item)
else if ( search(root.right, item) == True )
root.right = delete_element(root.right, item)
else if ( root.val == item )
{
// No child exists
if ( root.left == NULL and root.right == NULL )
delete root
// Only one child exists
else if ( root.left == NULL or root.right == NULL
{
if (root.left ==NULL)
return root.right
else
return root.left
}
// Both left and right child exists
else
{
TreeNode selected_node = root
while ( selected_node.left != NULL )
selected_node = selected_node.l
root.val = selected_node.val
root.left = delete_element(root.left, selected_node.val)
}
}
return root
}
APPLICATIONS OF DATA
STRUCTURE
• Databases use tree data structure for indexing.
• Tree data structure is used in file directory management.
• DNS uses tree data structure.
• Trees are used in several games like moves in chess.
• Decision-based algorithms in machine learning uses tree algorithms
Advantages and Disadvantages
ADVANTAGES
• Efficient searching
• Flexible size
• Easy to traverse
• Easy to maintain
• Fast insertion and deletion
DISADVANTAGES
• In balanced trees
• Limited flexibility
• Complexity
• Inefficient for certain operations

Unit Vi Trees

Uploaded by

Copyright:

Available Formats

Unit Vi Trees

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

Unit Vi Trees

Uploaded by

Copyright:

Available Formats

UNIT VI -TREES

• A node that has no children is called a leaf node.

This is a general tree because C has three child nodes

• There are three common ways to traverse a tree:

• It's a simple process in a binary tree. We just need to check if the

CASE 2 - It has only one child.

• We can't delete the root directly as there's a child node

You might also like