Wednesday, November 19, 2008

Tree Traversal

Example

A sorted binary tree

In this binary search tree,
  • Preorder traversal sequence: F, B, A, D, C, E, G, I, H
  • Inorder traversal sequence: A, B, C, D, E, F, G, H, I
    • Note that the inorder traversal of this binary search tree yields an ordered list
  • Postorder traversal sequence: A, C, E, D, B, H, I, G, F
  • Level-order traversal sequence: F, B, G, A, D, I, C, E, H

Sample implementations

preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)
if node.right ≠ null then preorder(node.right)
inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)
postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value


All sample implementations will require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.

We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree. In the case of using threads, this will allow for greatly improved inorder traversal, although retrieving the parent node required for preorder and postorder traversal will be slower than a simple stack based algorithm.

1 comment:

  1. if you want to view the edges b/w parent and its childs , simply save this image and view it in any image viewer

    ReplyDelete

Testing Challenge

Can you find more than 20 defects in the below image? Write your defects in the comments section.