Solving Problems with DFS: How This Algorithm Works in Everyday Tech

DFS, or Depth-First Search, is a way to explore trees and graphs by going deep before wide. Imagine you’re exploring a maze—instead of checking every possible path at each step, you pick one direction and keep going as far as possible before backtracking.

DFS can be performed in three main ways: Preorder, Inorder, and Postorder, each with its own specific use cases.

Let’s go through them one by one!

Different DFS orders (Preorder, Inorder, Postorder) have specific use cases in binary trees. Below are explanations, use cases, and TypeScript examples for each.

---

1️⃣ Preorder (Root → Left → Right)

Use Cases:

✅ Copying a tree (serializing & deserializing)

✅ Expression tree evaluation (e.g., + * 3 4 5)

✅ Generating a prefix expression

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

// Example Tree
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(preorder(root)); // Output: [1, 2, 3]

Example Use Case: Serializing a Tree

Preorder is useful for storing a tree as an array for easy reconstruction.

function serialize(root: TreeNode | null): string {
  if (!root) return "null";
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

console.log(serialize(root)); // Output: "1,2,null,null,3,null,null"

2️⃣ Inorder (Left → Root → Right)

Use Cases:

✅ Retrieving sorted values in a BST

✅ Solving problems where you need the next or previous element

✅ Used in threaded binary trees

function inorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

console.log(inorder(root)); // Output: [2, 1, 3] (Sorted if it's a BST)

Example Use Case: Finding Kth Smallest Element in a BST

function kthSmallest(root: TreeNode | null, k: number): number | null {
  let count = 0, result: number | null = null;

  function inorderHelper(node: TreeNode | null) {
    if (!node || result !== null) return;
    inorderHelper(node.left);
    count++;
    if (count === k) result = node.val;
    inorderHelper(node.right);
  }

  inorderHelper(root);
  return result;
}

console.log(kthSmallest(root, 2)); // Output: 2

3️⃣ Postorder (Left → Right → Root)

Use Cases:

✅ Deleting nodes safely (memory deallocation)

✅ Expression evaluation in trees

✅ Bottom-up problem-solving (dynamic programming on trees)

function postorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

console.log(postorder(root)); // Output: [2, 3, 1]

Example Use Case: Deleting a Tree

When deleting a tree, you should delete the children before the root to avoid memory leaks.

function deleteTree(root: TreeNode | null): void {
  if (!root) return;
  deleteTree(root.left);
  deleteTree(root.right);
  console.log(`Deleting node ${root.val}`);
}

deleteTree(root);
// Output:
// Deleting node 2
// Deleting node 3
// Deleting node 1

The Story of the Magic Tree and the Three Travelers 🌳✨

Once upon a time in the kingdom of Algoria, there stood a Magic Tree at the center of an enchanted forest. This tree contained powerful secrets hidden within its branches. Three travelers—a Scribe, a Treasure Hunter, and a Lumberjack—set out to explore its mysteries using different strategies.

---

1️⃣ The Scribe (Preorder - Root → Left → Right)

📜 Goal: The Scribe wanted to document the tree’s structure before anything else.

🔍 Method:

1. First, he noted down the root of the tree.

2. Then, he walked to the left branch and recorded what he saw.

3. Finally, he explored the right branch and wrote down its details.

📌 Example in TypeScript:

function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

💡 Real-Life Use Cases:

✅ Copying or saving a tree’s structure (Serialization)

✅ Expression tree evaluation (e.g., + * 3 4 5)

✅ Used in AI decision trees (like Minimax in Chess)

📖 Story Analogy:

Imagine if the Scribe wanted to rebuild a tree somewhere else—he would follow his notes exactly in the order he wrote them. This makes preorder useful for tree reconstruction.

---

2️⃣ The Treasure Hunter (Inorder - Left → Root → Right)

💰 Goal: The Treasure Hunter was looking for the hidden golden coins that were buried in increasing order in a tree.

🔍 Method:

1. He first checked the left side of the tree (since smaller coins were hidden there).

2. Then, he collected the coin at the root (current node).

3. Finally, he explored the right side, where larger coins were buried.

📌 Example in TypeScript:

function inorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

💡 Real-Life Use Cases:

✅ Retrieving sorted values from a Binary Search Tree (BST)

✅ Finding the "Kth smallest" element

✅ Used in database indexing for efficient searching

📖 Story Analogy:

Since the coins were placed in increasing order, the Treasure Hunter always found them from smallest to largest. This is exactly how inorder traversal retrieves elements in sorted order from a BST.

---

3️⃣ The Lumberjack (Postorder - Left → Right → Root)

🪵 Goal: The Lumberjack needed to cut down the entire tree, but he had to be careful. If he cut the root first, the tree might fall on him!

🔍 Method:

1. First, he chopped down the left branches.

2. Then, he cut the right branches.

3. Finally, once everything else was clear, he cut down the root.

📌 Example in TypeScript:

function postorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

💡 Real-Life Use Cases:

✅ Safely deleting a tree from memory

✅ Evaluating mathematical expressions in postfix notation

✅ Used in directory/file system deletion (removing files before directories)

📖 Story Analogy:

If the Lumberjack cut the root first, the whole tree could collapse dangerously. That’s why postorder ensures all dependencies (subtrees) are cleared before removing the root, making it perfect for deleting trees safely.

📌 Coding Questions (TypeScript)

1️⃣ Preorder Traversal

💡 Given a binary tree, return its Preorder traversal (Root → Left → Right).

typescript
CopyEdit
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function preorder(root: TreeNode | null): number[] {
  // Implement Preorder traversal
}

// Input Tree:
//      1
//     / \\
//    2   3
// Output: [1, 2, 3]

---

2️⃣ Inorder Traversal

💡 Given a binary tree, return its Inorder traversal (Left → Root → Right).

typescript
CopyEdit
function inorder(root: TreeNode | null): number[] {
  // Implement Inorder traversal
}

// Input Tree:
//      1
//     / \\
//    2   3
// Output: [2, 1, 3]

---

3️⃣ Postorder Traversal

💡 Given a binary tree, return its Postorder traversal (Left → Right → Root).

typescript
CopyEdit
function postorder(root: TreeNode | null): number[] {
  // Implement Postorder traversal
}

// Input Tree:
//      1
//     / \\
//    2   3
// Output: [2, 3, 1]

---

4️⃣ Construct a Binary Search Tree from a Preorder Traversal

💡 Given a Preorder traversal array of a BST, construct the BST and return its root.

typescript
CopyEdit
function bstFromPreorder(preorder: number[]): TreeNode | null {
  // Implement BST construction
}

// Example Input: [8, 5, 1, 7, 10, 12]
// Output: Root of BST

---

5️⃣ Kth Smallest Element in a BST (Use Inorder)

💡 Given a BST, return the Kth smallest element.

typescript
CopyEdit
function kthSmallest(root: TreeNode | null, k: number): number | null {
  // Implement using Inorder traversal
}

// Input BST:
//       3
//      / \\
//     1   4
//      \\
//       2
// k = 2
// Output: 2

---

6️⃣ Check if a Tree is Symmetric (Mirror Image)

💡 Use DFS to check if a binary tree is symmetric around its center.

typescript
CopyEdit
function isSymmetric(root: TreeNode | null): boolean {
  // Implement DFS symmetry check
}

// Input Tree:
//      1
//     / \\
//    2   2
//   / \\ / \\
//  3  4 4  3
// Output: true

---

🔄 Real-World Use Case Questions

1. How would you use DFS to find all paths from the root to the leaves in a binary tree?

2. How does DFS help in solving maze problems? Which DFS order would be best?

3. Can DFS be used to detect cycles in a graph? If so, how?

4. Which DFS traversal would you use to convert an expression tree into Postfix notation?

5. If you were designing a file system, which DFS order would you use for deleting a folder and its contents?

---

🚀 Challenge Problems

1. Implement an iterative DFS using a stack instead of recursion.

2. Modify the Preorder traversal to return nodes in a Zig-Zag order.

3. Given a binary tree, return the level with the maximum sum. (Hint: Use DFS to calculate the sum at each depth level.)

4. Convert a Binary Tree into a Doubly Linked List using Inorder traversal.

5. Find the lowest common ancestor of two nodes in a binary tree using DFS.

I’ll answer the questions and problems in the next post and update this one with the information.