CODEWITHSUNDEEP
binary-tree
CrazySynthax
CrazySynthax

Reputation: 15008

Tree Traversal Algorithms: why does the left node always comes before the right node?

You all know DFS algorithm. In the professional literature there are 3 flavors of DFS: Pre-Order (Node, left child, right child) In-Order (left child, node, right child) Post-Order (left child, right child, node)

In all these three algorithms/flavors, the left child always comes before the right child. Why? Is there something wrong with putting the right child before the left one?

Upvotes: 0

Views: 663

Answers (2)

James Raubenheimer
James Raubenheimer

Reputation: 21

The names left and right are arbitrary names given to the nodes of a tree. This convention matters in the case of defining binary search trees where the left subtree stores nodes smaller than the root and right subtree stores nodes larger than the root.

On a larger level, the convention of choosing left before right is most likely related to the way Latin alphabets are read from left and right.

Upvotes: 0

Sufian Latif
Sufian Latif

Reputation: 13356

[Disclaimer: I'm just stating my intuition here, so I can't provide references for my statement.]

I believe it has something to do with the order of the values and it's more of a convention than a rule. It makes more sense with binary search trees, where the value in the left child is less than the value in a node and the opposite for the right child. When we do an in-order traversal, we get the values in ascending order. Note that here's another convention: all literature about BSTs say that the smaller values go left and larger values go right; yet it wouldn't hurt at all if the definition said otherwise. Maybe the ascending order is considered as somewhat "natural" ordering (all the library sorting functions I've seen sorts values in ascending order by default).

If we had put the right subtree before the left in these three algorithms, they would produce the "traditional" sequence of the horizontally mirrored version of the same tree.

Maybe there is a parallel universe where people have developed the idea of BSTs where smaller values go to the right, and if they describe their traversal algorithms as right-before-left, the results produced by their traversals would be exactly the same as our "traditional" traversals!

Upvotes: 1

Related Questions