NETAJI SUBHAS UNIVERSITY
DATA STRUCTURE USING C
TOPIC:- BINARY TREE TRAVERSALS
GROUP PARTICIPANTS
1 SRIKANT PASWAN 2303249
2 GOUTAM MAHATO 2303089
3 SAHIL KR SHARMA 2303201
SUBMITTED TO:- DR. RANJAN MISHRA
Binary Tree
Traversals
A binary tree is a data structure where each node has at
most two children, referred to as the left and right child.
Depth-First Traversals
These traversals explore as far as possible along each
branch before backtracking.
1 In-Order Traversal 2 Pre-Order Traversal
Visits the left subtree, Visits the root, then
then the root, then the left subtree, then
the right subtree. the right subtree.
3 Post-Order Traversal
Visits the left subtree, then the right subtree, then the root.
In-Order Traversal
A commonly used traversal for binary search trees, as it
visits nodes in ascending order.
1 Visit Left Subtree
Recursively traverse the left subtree.
2 Visit Root
Process the data at the current node.
3 Visit Right Subtree
Recursively traverse the right subtree.
Pre-Order Traversal
Often used for creating a copy of the tree or for expressing the tree's structure.
Visit Root
Process the data at the current node.
Visit Left Subtree
Recursively traverse the left subtree.
Visit Right Subtree
Recursively traverse the right subtree.
Post-Order Traversal
Useful for deleting a tree, as it processes nodes after their subtrees.
Visit Left Subtree Visit Right Visit Root
Subtree
Breadth-First Traversal (Level-Order Traversa
Visits nodes level by level, starting from the root.
Queue Visualization
A queue data structure is used to store nodes to
be visited.
1. Enqueue the root node.
2. Dequeue a node and process it.
3. Enqueue its children.
4. Repeat steps 2-3 until the queue is empty.
Time Complexity of Travers
All depth-first and breadth-first traversals have the same
time complexity.
Depth-First Traversals Breadth-First Traversal
O(n), where n is the O(n), where n is the
number of nodes. number of nodes.
Space Complexity of
Traversals
The space complexity of traversals depends on the
recursion depth or queue size.
Depth-First Traversals Breadth-First Traversal
O(h), where h is the O(w), where w is the
height of the tree. maximum width of the
tree.
Applications of Binary Tree Traversals
Traversals are used in various algorithms and data structures.
Search Trees Compilers
In-order traversal for sorted output. Pre-order traversal for expression tree evaluation.
Conclusion
Binary tree traversals are fundamental techniques for
exploring and processing tree data structures.
