Binary search tree traversal implementation and complexity
Filed under Accolite
Free read 3 of 3Recursively visit left subtree, process current node, then right subtree. Produces sorted order for BST.
The question
Implement standard depth-first traversals (inorder, preorder, postorder) for a Binary Search Tree (BST) and state the time and space complexity for each.
Constraints
- The number of nodes in the tree is in the range [0, 10^4]
- -10^5 <= Node.val <= 10^5
Examples
- Input
- root = [2, 1, 3]
- Output
- inorder: [1, 2, 3], preorder: [2, 1, 3], postorder: [1, 3, 2]
- Why
- Inorder visits left-root-right, preorder visits root-left-right, postorder visits left-right-root.
Approach
Recursively visit left subtree, process current node, then right subtree. Produces sorted order for BST.
Preorder processes root first; Postorder processes root last after left and right subtrees.
Time is O(N) as every node is visited once. Space is O(H) recursion stack where H is tree height.
Tips
- What they are testing: Tests fundamental tree traversal recursion and understanding of call-stack space complexity.
- Common mistake: Stating space complexity is always O(log n), ignoring that degenerate/skewed trees degrade to O(n).
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.