Visualizer › Trees
Inorder Traversal
Visits the left subtree, then the node, then the right subtree. On a binary search tree it lists the keys in sorted order.
How it works
- Left → Root → Right.
- Space is the recursion depth h (tree height).
- Used to check if a tree is a valid BST.
Complexity
- Best time: O(n)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(h)
Code (Python)
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)Practise: Trees problems