TRAVERSAL ALGORITHMS
• WHAT IS A TREE?
• A tree is a collection of nodes.
• The collection can be empty; otherwise, a tree
consists of a distinguished node r, called the root,
and zero or more non-empty sub trees T1, T2, …, Tk
each of whose roots are connected by a directed
edge from r.
• A tree is a collection of N nodes, one of which is the
root and N-1 edges.
• The root of each subtree is said to be a
child of r and r is said to be the parent of
each subtree root.
• Leaves: nodes with no children /external
nodes.
• Internal Nodes: nodes with children.
• Siblings: nodes with the same parent.
• A preorder traversal prints the contents of a sorted tree in
preorder. The contents of the root node are printed first,
followed by the left subtree and finally the right subtree.
• In an InOrder traversal the contents of the sorted tree are
printed in order. It starts with lowest value first, and then
increasing its value as it traverses the tree. If the tree uses
strings or characters and would be increasing numerically
from 0 if the tree contains numerical values.
• A post order traversal prints the contents of a sorted tree in
post order. The contents of the left subtree are printed first
followed by right subtree and finally the root node.
• A path from node n1 to nk is defined as a
sequence of nodes n1, n2, …, nk such that ni is
the parent of ni+1 for 1<= i <= k.
• The length of this path is the number of edges
on the path namely k-1.
• The length of the path from a node to itself is
0.
• There is exactly one path from the root to each
node.
• Depth of node: the length of the unique path
from the root to a node.
• Depth of tree: The depth of a tree is equal to
the depth of its deepest leaf.
• Height of node: the length of the longest path
from a node to a leaf.
–All leaves have a height of 0
–The height of the root is equal to the depth of
the tree
BINARY TREE
• A binary tree is a tree in which no node
can have more than two children.
• Each node has an element, a reference to
a left child and a reference to a right child
• A binary tree is defined recursively: it consists
of a root, a left subtree, and a right subtree
• To traverse /walk the binary tree is to visit
each node in the binary tree exactly once
• Tree traversals are naturally recursive
TREE TRAVERSAL
• Traversing a tree means visiting each
node in a specified order
Breath First Search and Depth First Search
• There are generally two types of traversal:
• breadth first : Level Traversal. First access the root
element, then the children of the root element,
from left to right, then the grandchildren of the
root element, from left to right, and so on.
• depth first: There are three variants for depth
first: pre-order, in-order, and post-order.
Pre-order, in-order, post-order
• A pre-order traversal prints the contents of a sorted tree in pre-
order. The contents of the root node are printed first, followed by
the left subtree and finally the right subtree.
• In an in-order traversal the contents of the sorted tree are printed
in order. It starts with lowest value first, and then increasing its
value as it traverses the tree. If the tree uses strings or characters
and would be increasing numerically from 0 if the tree contains
numerical values.
• A post-order traversal prints the contents of a sorted tree in post
order. The contents of the left subtree are printed first followed by
right subtree and finally the root node.
PSEUDOCODES OF TRAVERSAL ALGORITHMS
