Binary Tree Traversals (Inorder, Preorder, Postorder, BFS)

Binary Tree Traversals: Visiting Every Node

Once a binary tree is constructed, we often need to visit each of its nodes in a systematic way. This process is called tree traversal. There are two main categories of traversal algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS), each with distinct patterns and applications.

---

1. Depth-First Search (DFS) Traversals

DFS algorithms explore as far as possible along each branch before backtracking. For binary trees, there are three common DFS orders:

1.1. Inorder Traversal (Left -> Root -> Right)

• Concept: Visit the left subtree, then the current node (root), then the right subtree.

• Key Feature: For a Binary Search Tree (BST), an inorder traversal visits nodes in ascending order of their values, effectively "sorting" the tree's elements.

• Pseudocode (Recursive):

  function inorder(node, visit) {
    if (!node) return;
    inorder(node.left, visit);    // Recursively visit left subtree
    visit(node.value);           // Visit current node
    inorder(node.right, visit);   // Recursively visit right subtree
  }
  

1.2. Preorder Traversal (Root -> Left -> Right)

• Concept: Visit the current node (root), then the left subtree, then the right subtree.

• Key Feature: Useful for creating a prefix expression of an expression tree or for serializing a tree (saving its structure to a file) because the root is processed before its children.

• Pseudocode (Recursive):

  function preorder(node, visit) {
    if (!node) return;
    visit(node.value);           // Visit current node
    preorder(node.left, visit);    // Recursively visit left subtree
    preorder(node.right, visit);   // Recursively visit right subtree
  }
  

1.3. Postorder Traversal (Left -> Right -> Root)

• Concept: Visit the left subtree, then the right subtree, then the current node (root).

• Key Feature: Useful for deleting nodes from a tree (ensuring children are deleted before their parent) or for evaluating postfix expressions in an expression tree.

• Pseudocode (Recursive):

  function postorder(node, visit) {
    if (!node) return;
    postorder(node.left, visit);    // Recursively visit left subtree
    postorder(node.right, visit);   // Recursively visit right subtree
    visit(node.value);           // Visit current node
  }
  

Note: Iterative versions of DFS traversals using an explicit stack are also common and can be used to avoid recursion depth limits in very deep trees.

---

2. Breadth-First Search (BFS) Traversal (Level-Order)

BFS explores the tree level by level, visiting all nodes at the current depth before moving to the next depth level.

• Concept: Visit all nodes at depth 0, then all nodes at depth 1, then all nodes at depth 2, and so on.

• Key Feature: Uses a queue data structure to keep track of nodes to visit.

• Pseudocode:

  function levelOrder(root, visit) {
    if (!root) return;
    const queue = [root]; // Initialize queue with the root node
  
    while (queue.length > 0) {
      const node = queue.shift(); // Get the first node from the queue
      visit(node.value);          // Visit current node
  
      if (node.left) {
        queue.push(node.left);    // Add left child to the queue
      }
      if (node.right) {
        queue.push(node.right);   // Add right child to the queue
      }
    }
  }
  

Note: Using Array.prototype.shift() in JavaScript can be O(N) for large arrays. For optimal O(1) dequeue performance in BFS, consider implementing a custom queue with a linked list or using a data structure optimized for queue operations.

---

3. Time and Space Complexity

• Time Complexity: All standard tree traversals (DFS and BFS) visit each node exactly once. Therefore, their time complexity is O(N), where N is the number of nodes in the tree.
• Space Complexity:
  • DFS (Recursive): O(H), where H is the height of the tree, due to the recursion call stack. In the worst case (a skewed tree), H can be N, leading to O(N) space.
  • DFS (Iterative with Stack): O(H) in the worst case, similar to recursive.
  • BFS (with Queue): O(W), where W is the maximum width of the tree (the maximum number of nodes at any single level). In the worst case (a complete binary tree), W can be N/2, leading to O(N) space.

---

Key Takeaway: Choosing the right tree traversal depends on the problem at hand. Inorder traversal is ideal for sorted output from BSTs, preorder for copying or serializing tree structures, postorder for deletion or expression evaluation, and BFS for level-by-level processing or finding the shortest path in an unweighted tree.

---