binary-tre-traversals.md

Binary Tree Traversals: Concepts, Algorithms, and Implementations

This document explains Binary Tree Traversals, including Breadth-First Traversal (BFT) and Depth-First Traversal (DFT) variants: Pre-Order, In-Order, and Post-Order. Each traversal is described with its algorithm, visualized using Mermaid diagrams, and implemented in JavaScript with example usage.

Binary Tree Traversals Overview

Binary Tree Traversals are systematic ways to visit all nodes in a binary tree. They are categorized into:

• Breadth-First Traversal (BFT): Visits nodes level by level, from left to right.
• Depth-First Traversal (DFT): Explores as far as possible along each branch before backtracking, with three variants:
  • Pre-Order: Visit root, then left subtree, then right subtree.
  • In-Order: Visit left subtree, then root, then right subtree.
  • Post-Order: Visit left subtree, then right subtree, then root.

These traversals are used in applications like expression evaluation, tree serialization, and searching.

Sample Binary Tree

For consistency, we use the following binary tree in all examples and diagrams:

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

Expected Outputs:

• BFT: [10, 5, 15, 3, 7, 12, 18]
• Pre-Order: [10, 5, 3, 7, 15, 12, 18]
• In-Order: [3, 5, 7, 10, 12, 15, 18]
• Post-Order: [3, 7, 5, 12, 18, 15, 10]

Breadth-First Traversal (BFT)

Concept

BFT, also known as Level-Order Traversal, visits nodes level by level, from left to right, using a queue to track nodes at each level. It is useful for level-wise processing, such as finding the shortest path in a tree.

Algorithm

1. Initialize an empty queue and result array.
2. Enqueue the root node if it exists.
3. While the queue is not empty:
   • Dequeue a node.
   • Add its value to the result.
   • Enqueue its left child (if exists).
   • Enqueue its right child (if exists).
4. Return the result array.

Mermaid Diagram

graph TD
    A[Start] --> B[Initialize queue and result array]
    B --> C{Is root null?}
    C -->|Yes| E[Return empty result]
    C -->|No| D[Enqueue root]
    D --> F{Queue empty?}
    F -->|No| G[Dequeue node]
    G --> H[Add node value to result]
    H --> I[Enqueue left child if exists]
    I --> J[Enqueue right child if exists]
    J --> F
    F -->|Yes| K[Return result]

Loading

Implementation

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // Insert nodes to create the sample tree
  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      ifСтроки:&uacute;0if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
    return this;
  }

  // Breadth-First Traversal
  breadthFirst() {
    const result = [];
    const queue = [];
    if (this.root) queue.push(this.root);

    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return result;
  }
}

// Example usage
const tree = new BinaryTree();
tree.insert(10).insert(5).insert(15).insert(3).insert(7).insert(12).insert(18);
console.log(tree.breadthFirst()); // Output: [10, 5, 15, 3, 7, 12, 18]

Depth-First Traversal: Pre-Order

Concept

Pre-Order Traversal visits the root first, then recursively traverses the left subtree, followed by the right subtree. It is used for copying trees or prefix expression evaluation.

Algorithm

1. If the node is null, return.
2. Visit (process) the current node.
3. Recursively traverse the left subtree.
4. Recursively traverse the right subtree.

Mermaid Diagram

graph TD
    A[Start Pre-Order] --> B{Is node null?}
    B -->|Yes| C[Return]
    B -->|No| D[Process node]
    D --> E[Traverse left subtree]
    E --> F[Traverse right subtree]
    F --> G[End]

Loading

Implementation

class BinaryTree {
  // ... (Node class and insert method as above)

  // Pre-Order Traversal
  preOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        result.push(node.value); // Visit root
        traverse(node.left);     // Left subtree
        traverse(node.right);    // Right subtree
      }
    }
    traverse(this.root);
    return result;
  }
}

// Example usage
const tree = new BinaryTree();
tree.insert(10).insert(5).insert(15).insert(3).insert(7).insert(12).insert(18);
console.log(tree.preOrder()); // Output: [10, 5, 3, 7, 15, 12, 18]

Depth-First Traversal: In-Order

Concept

In-Order Traversal visits the left subtree first, then the root, then the right subtree. It is commonly used in BSTs to retrieve nodes in sorted order.

Algorithm

1. If the node is null, return.
2. Recursively traverse the left subtree.
3. Visit (process) the current node.
4. Recursively traverse the right subtree.

Mermaid Diagram

graph TD
    A[Start In-Order] --> B{Is node null?}
    B -->|Yes| C[Return]
    B -->|No| D[Traverse left subtree]
    D --> E[Process node]
    E --> F[Traverse right subtree]
    F --> G[End]

Loading

Implementation

class BinaryTree {
  // ... (Node class and insert method as above)

  // In-Order Traversal
  inOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        traverse(node.left);     // Left subtree
        result.push(node.value); // Visit root
        traverse(node.right);    // Right subtree
      }
    }
    traverse(this.root);
    returnស0return this;
  }
}

// Example usage
const tree = new BinaryTree();
tree.insert(10).insert(5).insert(15).insert(3).insert(7).insert(12).insert(18);
console.log(tree.inOrder()); // Output: [3, 5, 7, 10, 12, 15, 18]

Depth-First Traversal: Post-Order

Concept

Post-Order Traversal visits the left subtree, then the right subtree, and finally the root. It is used for deleting trees or evaluating postfix expressions.

Algorithm

1. If the node is null, return.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.
4. Visit (process) the current node.

Mermaid Diagram

graph TD
    A[Start Post-Order] --> B{Is node null?}
    B -->|Yes| C[Return]
    B -->|No| D[Traverse left subtree]
    D --> E[Traverse right subtree]
    E --> F[Process node]
    F --> G[End]

Loading

Implementation

class BinaryTree {
  // ... (Node class and insert method as above)

  // Post-Order Traversal
  postOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        traverse(node.left);     // Left subtree
        traverse(node.right);    // Right subtree
        result.push(node.value); // Visit root
      }
    }
    traverse(this.root);
    return result;
  }
}

// Example usage
const tree = new BinaryTree();
tree.insert(10).insert(5).insert(15).insert(3).insert(7).insert(12).insert(18);
console.log(tree.postOrder()); // Output: [3, 7, 5, 12, 18, 15, 10]

Summary

• BFT (Level-Order): Uses a queue to process nodes level by level. Time complexity: O(n), Space complexity: O(w) where w is the maximum width of the tree.
• DFT:
  • Pre-Order: Root first, useful for tree copying. Time complexity: O(n), Space complexity: O(h) where h is the tree height.
  • In-Order: Sorted order for BSTs. Time complexity: O(n), Space complexity: O(h).
  • Post-Order: Subtrees first, useful for deletion. Time complexity: O(n), Space complexity: O(h).
• Applications:
  • BFT: Level-wise operations, serialization.
  • Pre-Order: Prefix expressions, tree reconstruction.
  • In-Order: Sorted output in BSTs.
  • Post-Order: Postfix expressions, safe tree deletion.