← Accolite questions

Binary search tree traversal implementation and complexity

Filed under Accolite

Free read 3 of 3

Recursively 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

  1. Recursively visit left subtree, process current node, then right subtree. Produces sorted order for BST.

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.