3-1 trees and binary trees.pptnd binaryf

trees and binary trees

1. Introduction
•Till now, we focussed only on linear data
structures such as stacks, queues and linked lists.
• But, in real-world situations, data relationships
are not always linear.
•Tree is one such non-linear data structure which
stores the data elements in a hierarchical manner
•. Each node of the tree stores a data value, and is
linked to other nodes in a hierarchical fashion.
•We will learn about the different types of trees and
their related operations.
•Most importantly, we will focus on binary tree and
its variants, which are widely used in the field of
computer science.

2. Basic Concept
•A tree is defined as a finite set
of elements or nodes, such
that
1.One of the nodes present at
the top of the tree is marked
as root node.
2.The remaining elements are
partitioned across multiple
subtrees present below the
root node.
•T is a simple tree containing
ten nodes with A being the
root node.
•The node A contains two
subtrees.
•The left subtree starts at node
B while the right subtree starts
at node C.
•Both the subtrees further
contain subtrees below
them, thus indicating
recursive nature of the tree
data structure.
•Each node in the tree has
zero or more child nodes.

3. Tree Terminology
Key Term Description Example (Tree T)
Node It is the data element of a tree. Apart from
storing a value, it also specifies links to
the other nodes.
A, B, C, D
Root It is the top node in a tree A
Parent A node that has one or more child nodes
present below it is referred as parent
node.
B is the parent node of D
and E
Child All nodes in a tree except the root node
are child nodes of their immediate
predecessor nodes.
H, I and J are child nodes
of E
Leaf It is the terminal node that does not have
any child nodes.
G, H, I, J and F are leaf
nodes
Internal
node
All nodes except root and leaf nodes are
referred as internal nodes.
B, C, D and E are internal
nodes
Sibling All the child nodes of a parent node are
referred as siblings.
D and E are siblings
Degree The degree of a node is the number of
subtrees coming out of the node.
Degree of A is 2
Degree of E is 3

4. Tree Terminology contd…
Key Term Description Example (Tree T)
Level All the tree nodes are present at different
levels. Root node is at level 0, its child
nodes are at level 1, and so on.
A is at level 0
B and C are at level 1
G, H, I, J are at level 3
Depth or
Height
It is the maximum level of a node in the
tree.
Depth of tree T is 3
Path It is the sequence of nodes from source
node till destination node.
A–B–E–J

5. Binary Tree
•Binary tree is one of the
most widely used non-
linear data structures in
the field of computer
science.
•It is a restricted form of a
general tree.
•The restriction that it
applies to a general tree
is that its nodes can have
a maximum degree of 2.
•That means, the nodes of
a binary tree can have
zero, one or two child
nodes but not more than
that.
•As shown in the above
binary tree, all nodes have
a maximum degree of 2.
• The maximum number of
nodes that can be present
at level n is 2
n
.

6. Strictly Binary Tree
•A binary tree is called strictly binary if all its nodes
barring the leaf nodes contain two child nodes.

7. Complete Binary Tree
•A binary tree of depth d is called complete binary tree if all its
levels from 0 to d–1 contain maximum possible number of nodes
and all the leaf nodes present at level d are placed towards the left
side.
• A complete binary tree of
level l will have maximum
2l nodes at each level,
where l starts from 0.
•Any binary tree with n
nodes will have at the
most n+1 null branches.
•The total number of edges
in a complete binary tree
with n terminal nodes are
2(n-1). t level d are placed
towards the left side.

8. Perfect Binary Tree
•A binary tree is called perfect binary tree if all its
leaf nodes are at the lowest level and all the non-
leaf nodes contain two child nodes.

9. Balanced Binary Tree
•A binary tree is called balanced binary tree if the
depths of the subtrees of all its nodes do not differ
by more than 1.

10. Left Skewed Balanced Binary Tree
•If the right sub-tree is missing in every node of a
tree we call it as left skewed tree.

11. Right Skewed Balanced Binary Tree
•If the left sub-tree is missing in every node of a
tree we call it is right sub-tree.

12. Binary Tree Representation
•The sequential representation of binary trees
is done by using arrays
•The linked representation is done by using
linked lists.

13. Array Representation
•One-dimensional array is used for storing the
node elements.
•The following rules are applied while storing
the node elements in the array:
1.The root node is stored at the first position in
the array while its left and right child nodes are
stored at the successive positions.
2.If a node is stored at index location i then its
left child node will be stored at location 2i+1
while the right child node will be stored at
location 2i+2.

14. Example binary tree
•T
1
is a binary tree containing seven nodes with A being the
root node.
•B and C are the left and right child nodes of A respectively.
•Let us apply the rules explained earlier to arrive at the array
representation of binary tree T
1
.

15. Array representation binary tree T
1
•the array index values for each of the tree nodes.
•Array A is used for storing the node values.

16. Array representation binary tree T
1 contd..
•modify the binary tree T
1
a little by deleting nodes E and F.

17. Array Representation advantage
•The only advantage with this type of
representation is that the direct access to any
node can be possible and finding the parent or
left children of any particular node is fast
because of the random access.

18. Array Representation disadvantage
•In this type of representation the maximum depth of the tree
has to be fixed Because we have decide the array size.
•If we choose the array size quite larger than the depth of the
tree, then it will be wastage of the memory. And if we choose
array size lesser than the depth of the tree then we will be
unable to represent some part of the tree.
•The insertions and deletion of any node in the tree will be
costlier as other nodes has to be adjusted at appropriate
positions so that the meaning of binary tree can be preserved.
•The major disadvantage with this type of representation is
wastage of memory.
•It efficiently utilizes the memory space only when the tree is a
complete binary tree. Otherwise, there are always some
memory locations lying vacant in the array.

19. Linked Representation of binary tree
•To avoid the disadvantages associated with array
representation, linked representation is used for
implementing binary trees.
•It uses a linked list for storing the node elements.
•Each tree node is represented with the help of the
linked list node comprising of the following fields:
1.INFO Stores the value of the tree node.
2.LEFT Stores a pointer to the left child.
3.RIGHT Stores a pointer to the right child.
•In addition, there is a special pointer that points at the
root node.

20. Linked list representation of binary tree contd..
•Below figure shows how linked list is used for representing
a binary tree in memory

21. Linked Representation of binary tree contd..
•The linked representation of binary tree uses
dynamic memory allocation technique for
adding new nodes to the tree.
•It reserves only that much amount of memory
space as is required for storing its node values.
•Thus, linked representation is more efficient as
compared to array representation.

22. Linked Representation of binary tree advantages
•This representation is superior to our array
representation as there is no wastage of memory.
•There is no need to have prior knowledge of
depth of the tree.
•Using dynamic memory concept one can create
as much memory(nodes) as required.
•By chance if some nodes are unutilized one can
delete the nodes by making the address free.
•Insertions and deletions which are the most
common operations can be done without moving
the nodes.

23. Linked Representation of binary tree disadvantages
•This representation does not provide direct
access to a node and special algorithms are
required.
• This representation needs additional space in
each node for storing the left and right sub-
trees.

24. Binary Tree Traversal
•Traversal is the process of visiting the various elements of a
data structure.
•Binary tree traversal can be performed using three methods:
1.Preorder
2.Inorder
3.Postorder

25. Binary Tree Preorder Traversal
•The preorder traversal method operations:
a)Process the root node (N).
b)Traverse the left subtree of N (L).
c)Traverse the right subtree of N (R).
•A-B-C-D-E data at the root node will be printed first then we move on the
left sub-tree and go on printing the data till we reach to the left most node.
•Print the data at that node and then move to the right sub- tree.
•Follow the same principle at each sub-tree and go on printing the data
accordingly.

26. Binary Tree Inorder tranersal
•The inorder traversal method operations:
a)Traverse the left subtree of N (L).
b)Process the root node (N).
c)Traverse the right subtree of N (R).
C-B-A-D-E is the inorder traversal i.e. first we go towards the
leftmost node. i.e. C so print that node C. Then go back to the
node B and print B. Then root node A then move towards the
right sub-tree print D and finally E.

27. Binary Tree Post order traversal
•traversal method operations:
a)Traverse the left subtree of N (L).
b)Traverse the right subtree of N (R).
c)Process the root node (N).
•postorder traversal is C-D-B-E-A.
•Left|Right|Root principle i.e. move to the leftmost node, if right
sub-tree is there or not if not then print the leftmost node, if
right sub-tree is there move towards the right most node. The
key idea here is that at each sub-tree we are following the Left|
Right|Root principle and print the data accordingly.

28. Binary Tree Traversal contd…
•Preorder traversal sequence
A–B–D–E–G–C–F
•Inorder traversal sequence
D–B–G–E–A–C–F
•Postorder traversal
sequence
D–G–E–B–F–C–A

29. Binary Tree Traversal contd…
•The pre-order traversal is: A-B-D-E-H-C-F-G-I-K-J
•The in-order traversal is : D-B-H-E-A-F-C-K-I-G-J
•The post-order traversal is:D-H-E-B-F-K-I-J-G-C-A