Cacher is the code snippet organizer for pro developers

Tree Traversal

• DFT: Depth First Traversals
  • Inorder (left, root, right)
  • Preorder (root, left, right)
  • Postorder (left, right, root)

Inorder Traversal

     1
  2    3
4  5

• Traversal: 4, 2, 5, 1, 3
• Algorithm:
  • Traverse the left subtree (call inorder(left-subtree))
  • Visit the root
  • Traverse the right subtree (call inorder(right-subtree))
• Uses

Preorder Traversal

• Traversal (from diagram above): 1, 2, 4, 5, 3
• Algorithm:
  • Visit the root
  • Traverse the left subtree (call preorder(left-subtree))
  • Traverse the right subtree (call preorder(right-subtree))
• Uses:
  • Used to create a copy of the tree
  • Used to obtain prefix expressions of an expression tree

Postorder Traversal

• Traversal (from the diagram above): 4, 5, 2, 3, 1
• Algorithm:
  • Traverse the left-subtree (call postorder(left-subtree))
  • Traverse the right-subtree (call postorder(right-subtree))
  • Visit the root
• Uses
  • Used to delete the tree