Traversal Operations in Binary Trees

Understanding Tree Traversals

Tree traversal is the process of visiting each node in a tree exactly once. There are several ways to traverse a binary tree, each with different applications:

• In-order Traversal: Visit left subtree, then root, then right subtree (LNR)
• Pre-order Traversal: Visit root, then left subtree, then right subtree (NLR)
• Post-order Traversal: Visit left subtree, then right subtree, then root (LRN)
• Level-order Traversal: Visit nodes level by level, from left to right

In-order Traversal

In-order traversal visits the left subtree, then the root, then the right subtree. For a binary search tree, this produces nodes in ascending order.

inOrderTraversal(node: TreeNode | null): number[] {
  const result: number[] = [];
  
  const traverse = (node: TreeNode | null) => {
    if (node !== null) {
      // First, visit left subtree
      traverse(node.left);
      
      // Then, visit the node itself
      result.push(node.value);
      
      // Finally, visit right subtree
      traverse(node.right);
    }
  };
  
  traverse(node);
  return result;
}

Pre-order Traversal

Pre-order traversal visits the root, then the left subtree, then the right subtree. This is useful for creating a copy of the tree or for getting a prefix expression of an expression tree.

preOrderTraversal(node: TreeNode | null): number[] {
  const result: number[] = [];
  
  const traverse = (node: TreeNode | null) => {
    if (node !== null) {
      // First, visit the node itself
      result.push(node.value);
      
      // Then, visit left subtree
      traverse(node.left);
      
      // Finally, visit right subtree
      traverse(node.right);
    }
  };
  
  traverse(node);
  return result;
}

Post-order Traversal

Post-order traversal visits the left subtree, then the right subtree, then the root. This is useful for deleting a tree or for getting a postfix expression of an expression tree.

postOrderTraversal(node: TreeNode | null): number[] {
  const result: number[] = [];
  
  const traverse = (node: TreeNode | null) => {
    if (node !== null) {
      // First, visit left subtree
      traverse(node.left);
      
      // Then, visit right subtree
      traverse(node.right);
      
      // Finally, visit the node itself
      result.push(node.value);
    }
  };
  
  traverse(node);
  return result;
}

Level-order Traversal

Level-order traversal visits nodes level by level, from left to right. This is also known as breadth-first search (BFS) and is implemented using a queue.

levelOrderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  
  if (root === null) {
    return result;
  }
  
  // Create a queue and enqueue the root
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    // Dequeue a node
    const node = queue.shift()!;
    
    // Process the node
    result.push(node.value);
    
    // Enqueue the left child if it exists
    if (node.left !== null) {
      queue.push(node.left);
    }
    
    // Enqueue the right child if it exists
    if (node.right !== null) {
      queue.push(node.right);
    }
  }
  
  return result;
}

Example

Let's consider the following binary search tree:

        10
       /  \
      5    15
     / \  / \
    3   7 12 18

The different traversals would produce:

• In-order: [3, 5, 7, 10, 12, 15, 18] (sorted order for a BST)
• Pre-order: [10, 5, 3, 7, 15, 12, 18]
• Post-order: [3, 7, 5, 12, 18, 15, 10]
• Level-order: [10, 5, 15, 3, 7, 12, 18]

Applications of Tree Traversals

• In-order: Used to get elements of a BST in sorted order.
• Pre-order: Used to create a copy of the tree or to get a prefix expression of an expression tree.
• Post-order: Used to delete a tree or to get a postfix expression of an expression tree.
• Level-order: Used in level-order applications like printing a tree level by level.

Time and Space Complexity

Time Complexity: O(n) for all traversals, where n is the number of nodes in the tree, as each node is visited exactly once.

Space Complexity: O(h) for recursive in-order, pre-order, and post-order traversals due to the call stack, where h is the height of the tree. For level-order traversal, the space complexity is O(w), where w is the maximum width of the tree.