• Tree:
  • A connected graph with no circuits
• Structures for Trees:
  • Can use both contiguous and linked structures

• Defined:
  • Moving through the vertices in a tree, following the edges
• Trees of Interest:
  • Binary Trees
  • Other N-ary Trees
  • General Trees

• The Three Parts:
  • Traversal of a single node
  • Traversal of a left subtree
  • Traversal of a right subtree
• Traversal Orders:
  • Preorder - traverse the root node, then the left subtree, then the right subtree
  • Inorder - traverse the left subtree, then the root node, then the right subtree
  • Postorder - traverse the left subtree, then the right subtree, then the root node

Pseudocode for Inorder Traversal

    inOrder(current)
    {
        if (current != null) 
        {
            inOrder(current's left)

	    print(current's data)

	    inOrder(current's right)
        }
    }