DSA In-order Traversal
In-order Traversal of Binary Trees
arranged in A variation of Depth First Search is traversal, in which a certain order is visited at each node. Go here to learn more about traversals of binary trees in general.
To see how to perform an in-order traversal of a binary tree, play the animation below.
==== example mukavu ====
After visiting the root node, In-order Traversal performs a recursive In-order Traversal of the left subtree before performing a recursive In-order Traversal of the right subtree. This traversal returns values in ascending order and is primarily used for Binary Search Trees.
What makes this traverse “in” order, is that the node is visited in between the recursive function calls. The left subtree’s in-order traversal comes after the node, and the right subtree’s in-order traversal comes before it.
This is how the code for In-order Traversal looks like:
Example
Python:
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
Until that argument is None and the method returns (lines 2-3), the inOrderTraversal() function repeatedly calls itself with the current left child node as an argument (line 4).
When node C’s left child (because C has no left child) is supplied as an argument, the argument node is None for the first time.
Following that, line 5 prints the data portion of node C, indicating that ‘C’ is displayed first.
Next, the function call returns without doing anything else because the argument (line 6) for node C’s right child is None.
The previous inOrderTraversal() function calls continue to execute after ‘C’ is displayed, printing ‘A’, ‘D’, ‘R’, and so on.
