Learn Algorithms - Tree Traversal

Tree Traversal

Identify Tree Elements First..

Introduction..

Here we are going to talk about Tree traversal. In computer science, that refers to the process of visiting each node in a tree structure,exactly once, in a systematic way. As in the above diagram nodes are indicated as circles. These kind of traversals are classified by the order in which the nodes are visited. In this post we are going to talk about traversing using algorithms in binary trees. this processes are not only true for the binary trees. Those can be generalized to the other trees as well (i.e ternary trees.).

Traversing in a Binary Tree..

To traverse a binary tree there exist several different ways. Starting at the root of a binary tree( First node of the tree), there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node.

Recursion and Co-Recursion..

Recursion..

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Resource : http://en.wikipedia.org/wiki/Recursion_(computer_science)
Co-Recursion..

In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. Some authors refer to this as generative recursion.

Resource : http://en.wikipedia.org/wiki/Corecursion

Traversing a tree can be done in several ways. Normally how we do is we use iterating method to visit all the nodes in the tree. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred – stored in some way for later visiting. We do this using either stack or a queue. those data structures have implemented using LIFO (Last In First Out) and FIFO (First inf Last Out) principles. As we know tree is a recursively defined data structure. Its known as self-referential data structures. In a tree traversing can be done in either recursion or either in corecursion manner. Usually we use recursion to traverse the tree.

There are two strategies that we used to traverse a tree. One is call Depth First and Other one is call the Breadth First.For the purpose of illustration, it is assumed that left nodes always have priority over right nodes. This ordering can be reversed as long as the same ordering is assumed for all traversal methods. Depth First Search can be easily implemented using a stack where as the breadth first traversal can be easily implemented using a queue.

Depth-first traversal is easily implemented via a stack, including recursively (via the call stack), while breadth-first traversal is easily implemented via a queue, including corecursively. For the purpose of illustration, it is assumed that left nodes always have priority over right nodes. This ordering can be reversed as long as the same ordering is assumed for all traversal methods.

Depth First