[go: up one dir, main page]
Scribd
Upload
18 views1 page

Tree Traversal

DS

Uploaded by

kamakshi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
18 views1 page

Tree Traversal

DS

Uploaded by

kamakshi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Tree Traversal:

Tree: Trees are hierarchical data structures composed of nodes connected by edges,
where each node may have zero or more child nodes and one parent node (except for
the root node).
Example:

Tree traversal: Tree Traversal refers to the process of visiting each node in a tree
data structure exactly once.
Tree traversal is categorized into:
1. Depth first search (DFS): The depth-first search (DFS) is a method of traversing
or searching data structures composed of trees or graphs.
There are three main types of tree traversal:
Pre-order Traversal: In Pre-order traversal, we visit the root node first, then traverse
the left sub-tree, and finally, traverse the right sub-tree. The order of traversal is Root-
Left-Right.
In-order Traversal: In in-order traversal, we first traverse the left sub-tree, then visit
the root node, and finally, traverse the right sub-tree. The order of traversal is Left-
Root-Right.
Post-order Traversal: In post-order traversal, we first traverse the left sub-tree, then
the right sub-tree, and finally, visit the root node. The order of traversal is Left-Right-
Root
2. Breadth-first tree traversal: Breadth-first tree traversal is also known as level-
order traversal, it is a tree traversal technique used to visit all the nodes of a tree level
by level. In this traversal, nodes at the same level are visited before moving on to the
next level.
Example:
Pre-order: (Root-Left-Right) - 1 -> 2 -> 3
In-order: (Left-Root-Right) - 2 -> 1 -> 3
Post-order: (Left-Right-Root) -2-> 3 ->1
BFS: 1 -> 2 -> 3

Applications of tree traversal:


Searching and Retrieval: Tree traversal is commonly used to search for specific
elements in a tree. For instance, in binary search trees (BSTs), an in-order traversal
can efficiently retrieve the elements in sorted order.
Expression Evaluation: Expression trees are used to represent mathematical
expressions. Traversing an expression tree helps in evaluating the expressions
effectively, simplifying complex calculations.
Binary Heap Operations: Heap data structures, like binary heaps, are often used in
priority queues and sorting algorithms. Traversing a heap allows for efficient access
to the minimum or maximum element.
Graph Algorithms: Trees are a special type of graphs. Tree traversal algorithms like
depth-first search (DFS) and breadth-first search (BFS) can be adapted for graph
traversal, path finding, and cycle detection.

You might also like