Tree Search

Such traversals are classified by the order in which the nodes are visited.

The following algorithms are described for a Binary Tree , but they may be generalized to other trees.

TRAVERSAL METHODS

Say we have a tree node structure which contains a value value and references left and right to its two children. Then we can write the following function:

pre-order (prefix) traversal



visit(node)

    print node.value

    if node.left  != null then visit(node.left)

    if node.right != null then visit(node.right)

This Recursive Algorithm prints the values in the tree in pre-order. In pre-order, each node is visited before any of its children. Similarly, if the print statement were last, each node would be visited after all of its children, and the values would be printed in '''post-order'''. In both cases, values in the left subtree are printed before values in the right subtree.

post-order (postfix) traversal



visit(node)

    if node.left  != null then visit(node.left)

    if node.right != null then visit(node.right)

    print node.value

in-order (infix) traversal



visit(node)

    if node.left  != null then visit(node.left)

    print node.value

    if node.right != null then visit(node.right)

An in-order traversal, as above, visits each node between the nodes in its left subtree and the nodes in its right subtree. This is a particularly common way of traversing a Binary Search Tree , because it gives the values in increasing order.

To see why this is the case, note that if n is a node in a binary search tree, then everything in n's left subtree is less than n, and everything in n's right subtree is greater than or equal to n. Thus, if we visit the left subtree in order, using a recursive call, and then visit n, and then visit the right subtree in order, we have visited the entire subtree rooted at n in order. We can assume the recursive calls correctly visit the subtrees in order using the mathematical principle of Structural Induction .

If instead we visit the right subtree, then the current node, then the left subtree, this produces the opposite order as in-order traversal, sometimes called a reverse in-order or '''reverse-order''' traversal.

level order traversal



visitlevel(S)

  T = Set()

  for each node in S   

    print node.Value

    if (node->left != null)

       T.insert(node->left)

    if (node->right != null)

       T.insert(node->right)

  if ( T.empty() != true)

    visitlevel(T)



visit(root)

  S = Set()

  S.insert(root)

  visitlevel(S)

This prints the nodes in the order of their depth from the root. See the iterative version below.

EXAMPLES

FUNCTIONAL TRAVERSAL

We could perform the same traversals in a functional language like Haskell using code like this:

	CATEGORIES ABOUT TREE TRAVERSAL

	trees structure

	articles with example haskell code

	articles with example pseudocode

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Tree Search