BST Traversal

Tags

BST Traversal

Category

Binary Search Trees (BST)

Difficulty

Medium

Problem Statement

Given a Binary Search Tree (BST), implement three classic depth-first traversal methods: in-order, pre-order, and post-order. Each traversal visits every node exactly once but in a different order, and the result is an array of node values in the order they were visited.

  • In-order: left subtree, current node, right subtree
  • Pre-order: current node, left subtree, right subtree
  • Post-order: left subtree, right subtree, current node

Intuition

Each traversal order captures a different structural perspective of the tree. In-order traversal on a BST produces values in sorted (ascending) order because the BST property guarantees that all left descendants are smaller and all right descendants are larger. Pre-order traversal captures the structure needed to reconstruct the tree (root first, then children). Post-order traversal processes children before parents, which is useful for deletion or bottom-up computations.

The recursive nature of trees maps directly to recursive function calls: at each node, you choose when to "visit" the current node relative to recursing on its children.

Approach

  1. Start at the root node.
  2. For in-order traversal:
    • Recursively traverse the left subtree.
    • Append the current node's value to the result array.
    • Recursively traverse the right subtree.
  3. For pre-order traversal:
    • Append the current node's value to the result array.
    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree.
  4. For post-order traversal:
    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree.
    • Append the current node's value to the result array.
  5. Base case: if the current node is null, return immediately.

Pseudocode

function inOrderTraverse(node, array):
    if node is null:
        return
    inOrderTraverse(node.left, array)
    array.append(node.value)
    inOrderTraverse(node.right, array)

function preOrderTraverse(node, array):
    if node is null:
        return
    array.append(node.value)
    preOrderTraverse(node.left, array)
    preOrderTraverse(node.right, array)

function postOrderTraverse(node, array):
    if node is null:
        return
    postOrderTraverse(node.left, array)
    postOrderTraverse(node.right, array)
    array.append(node.value)

Time & Space Complexity

  • Time: O(n) for all three traversals, where n is the number of nodes. Every node is visited exactly once.
  • Space: O(n) total. The result array holds n values. The call stack uses O(h) space where h is the height of the tree (O(log n) for balanced, O(n) for skewed).

Key Insights

  • In-order traversal of a BST always yields values in sorted ascending order. This is a direct consequence of the BST invariant.
  • Pre-order traversal output can be used to uniquely reconstruct the original BST.
  • Post-order traversal is useful when you need to process children before their parent (e.g., computing subtree sizes, freeing memory).
  • All three traversals can also be implemented iteratively using an explicit stack, which avoids potential stack overflow for very deep trees.

Edge Cases

  • Empty tree (root is null): return an empty array for all traversals.
  • Single-node tree: all three traversals return an array with just that one value.
  • Completely left-skewed or right-skewed tree: recursion depth equals n, which may cause stack overflow for very large n.
  • Tree with duplicate values (if the BST allows them): traversal order depends on where duplicates are placed (left or right subtree).

Linked mentions