inorder

Inorder traversal, often abbreviated as LNR, is a method for visiting nodes in a binary tree. It visits the left subtree first, then the node itself, and finally the right subtree. This ordering is also called symmetric traversal in some texts.

In binary search trees, an inorder traversal yields the keys in nondecreasing order, making it a natural way to extract a sorted list from a BST. For general binary trees, inorder provides a depth-first ordering that depends on the tree’s structure rather than on a key order.

A common recursive implementation visits the left child, processes the current node, and then visits the right child. Pseudocode often appears as: if node is not null, inorder(left), visit(node), inorder(right). The time complexity is O(n) and the auxiliary space complexity is O(h), where h is the tree height, due to the call stack.

An iterative approach uses an explicit stack to emulate recursion. The algorithm traverses to the leftmost node, pushing nodes along the way, then processes nodes and explores right subtrees as needed. This also runs in O(n) time with O(h) space.

A space-optimized variant, Morris traversal, modifies the tree structure temporarily to achieve O(1) extra space while still visiting nodes in inorder. It is more complex but useful when memory is at a premium.

Applications include generating sorted sequences from BSTs, converting binary trees to infix expressions in expression trees, and providing a foundational step for more advanced tree algorithms. Inorder is one of the standard tree traversals, alongside preorder and postorder.