2
votes

There is lot of content on the web stating that there are four tree traversal algorithms:

  • Depth First Search - InOrder (left-Root-right)
  • PreOrder (Root-left-right)
  • PostOrder(left-right-Root)
  • Breadth First Search - Level Order Traversal

Are these tree traversals obtained due to the concept of Binary Search Tree? (i.e., where the left subtree is smaller than right subtree and hence we traverse left before right?)

What about other combinations of tree traversals? For example: Right-Root-Left, Right-Left-Root, Root-Right-Left, and in Level-order we traverse from Right node?

If the above combinations of tree traversals are valid, will the time-complexity of tree-travels remain the same with respect to their left-first counterparts?

In real-world applications, do they use the right-first combinations of tree-traversals? Give examples.

2
You can also traversal the children of each node in random order. So there are a lot of other orders that you can think of (e.g. dependent of some kind of value of the child-nodes). So thre are 3 very common traversal orders and a lot of not so common ones.MrSmith42
If you have a binary search tree that you want to traverse in reverse order, you would use "right-root-left". It's just a reverse inorder traversal. And, yes, its computational complexity is the same as a traditional inorder traversal.Jim Mischel
Excellent question. Deserves more attention and responses. If what ruakh said in his answer is true about the other types of traversals, I wonder why they aren't discussed or taught as much as their counterparts.Hemanth Annavarapu

2 Answers

2
votes

Are these tree traversals obtained due to the concept of Binary Search Tree? (i.e., where left subtree is smaller than right subtree and hence we traverse left before right?)

Apparently not, because of those four traversals, the only one that really makes sense for a binary search tree is the 'inorder' traversal. The other three would read elements out of order.

Rather, I think it's that the convention for binary trees (at least in English-speaking countries) is to call the first child "left" and the second child "right", and to draw them accordingly when drawing visual representations. That convention applies both to binary search trees (where the first child contains all values that come before the parent's, and the second child contains all values that come after it) and to tree traversals (where we traverse the first child before the second).

What about other combinations of tree traversals? Example: Right-Root-Left, Right-Left-Root, Root-Right-Left, and in Level-order we traverse from Right node?

All totally possible. You could also traverse in a zigzag order, where sometimes you process the left child before the right child, and sometimes the reverse. (Or, put another way: where sometimes you describe the first child as "left" and the second child as "right", and sometimes the reverse.)

If the above combinations of tree traversals are valid, I guess the time-complexity of tree-travels will remain the same with respect to their left-first counterparts?

If your tree structure involves explicit pointers to children and so on, and your traversals follow those pointers, then — yes: "left" and "right" are just names, and don't affect the theoretical time-complexity. But if your tree structure is implicit (for example, as is typically done with binary heaps), then it might depend on the details.

In real-world applications, do they use the right-first combinations of tree-traversals? Give examples.

I'm sure there exist real-world applications that involve traversing a binary search tree from greatest to least element. In such an application, the terms "left" and "right" are likely to be assigned based on the convention that smaller values come first (on the left), so the traversals from greatest-to-least will start at the "end" of the tree, meaning its rightmost node, and proceed toward its "start", meaning its leftmost.

However, the most obvious instance of this sort of thing would be querying a SQL table with an ORDER BY ... DESC clause; and I believe the major SQL implementations use sorted B-trees, not specifically binary search trees, so they probably don't use the terms "left" and "right".

0
votes

There is one type of traversal en.wikipedia doesn't account for, too:

Height traversal. Starting with the leafs/nodes at height 0, go up the tree height by height.

Uselessness and adversity of implementation left as a pointless exercise.