／var／logmarcus chiu

Tree Traversal (Depth／Breadth-First - Pre-Order, In-Order, Out-Order, Post-Order)

Created on · Last Modified on

Depth-First Traversals

  • similar to Depth First Search (DFS)
  • general recursive pattern for traversing a binary tree is this: At node N do the following in any order:
    • L - recursively traverse left subtree
    • R - recursively traverse right subtree
    • N - process N itself
  • left-to-right traversal - L is done before R
  • right-to-left traversal - R is done before L
  • types of depth-first search traversals:
    • Pre-Order (NLR)
    • In-Order (LNR)
    • Out-Order (RNL)
    • Post-Order (LRN)

Breadth-First Traversal