CODEWITHSUNDEEP
algorithmtree
jcm
jcm

Reputation: 5659

Traversing a tree from right to left

I was reading the book "Fundamentals of Algorithms" by Brassard and Bratley and there is a statement in the section on tree traversals that says:

Preorder, postorder and inorder traversals explore the tree from left to right. Three corresponding techniques explore the tree from right to left.

What does it mean to traverse from right to left? My guess is that they mean tat a right-to-left preorder traversal is equivalent to a regular left-to-right postorder traversal? And that the inorder for both left-to-right and right-to-left are the exact same algorithm?

Upvotes: 1

Views: 2612

Answers (2)

rici
rici

Reputation: 241931

Here's a simple tree, a single node with two leaves:

        Mom
         ^
        / \
       /   \
      /     \
    Sally   Bob

Since there are three labels, there are six (three factorial) possible orders. Three of these correspond to left-to-right traversals, where Sally is named before Bob:

  • Mom, Sally, Bob ← preorder. Mom is before the kids.
  • Sally, Bob, Mom ← postorder. Mom is after the kids.
  • Sally, Mom, Bob ← inorder. Mom is between the kids.

If we were to visit the kids in the opposite order (Bob first), then we would have right-to-left (RTL) traversal. (Bob's on the right, right?) Again, three possibilities:

  • Mom, Bob, Sally ← RTL preorder. Mom is before the kids.
  • Bob, Sally, Mom ← RTL postorder. Mom is after the kids.
  • Bob, Mom, Sally ← RTL inorder. Mom is between the kids.

All of the above are depth-first traversals. That means that if we visit a child node (Sally, for example), we complete traverse that node before continuing with whatever is to be traversed next.

Upvotes: 0

Salvador Dali
Salvador Dali

Reputation: 222929

I am not sure I understood all the questions, so I will answer only one.

What does it mean to traverse from right to left?

All of these tree traversal methods require recursion. In recursion you need to do something with element and traverse left/right tree. You have *L*R*. You can insert your do something instead of one of the *. And will get your pre/in/pos - order.

Upvotes: 0

Related Questions