Skip to main content
Engineering LibreTexts

5.1: Traversal

  • Page ID
    47900
  • Many problems require we visit the nodes of a tree in a systematic way: tasks such as counting how many nodes exist or finding the maximum element. Three different methods are possible for binary trees: preorder, postorder, and in-order, which all do the same three things: recursively traverse both the left and right subtrees and visit the current node. The difference is when the algorithm visits the current node:

    • preorder: Current node, left subtree, right subtree (DLR)
    • postorder: Left subtree, right subtree, current node (LRD)
    • in-order: Left subtree, current node, right subtree (LDR)
    • levelorder: Level by level, from left to right, starting from the root node.

    Note

    Visit means performing some operation involving the current node of a tree, like incrementing a counter or checking if the value of the current node is greater than any other recorded.

    • Was this article helpful?