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

[![](https://cdn.hashnode.com/res/hashnode/image/upload/v1740964172054/7a775687-5e0b-4f0a-9165-bb3df6f9b593.png align="center")](https://www.blog.codeinmotion.io/p/leetcode-patterns)

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**

```tsx
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.

```tsx
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**

```tsx
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**

```tsx
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)**

```tsx
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.

```typescript
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.

![A Scribe wanted to document the tree’s structure before anything else.](https://th.bing.com/th/id/OIG1.ebLSDEsc_VPODoVSG2Zn?pid=ImgGn align="left")

🔍 **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**:

```tsx
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.  

![The Treasure Hunter was looking for the hidden golden coins that were buried in increasing order in a tree.](https://th.bing.com/th/id/OIG4.2JfJdFYfuEjASPyV4P_r?pid=ImgGn align="left")

🔍 **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**:

```tsx

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!

![The Lumberjack needed to cut down the entire tree, after cutting down the branches](https://th.bing.com/th/id/OIG2.JIu3WnMa.3tGrPXrhiNR?w=1024&h=1024&rs=1&pid=ImgDetMain align="left")

  
🔍 **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**:

```tsx
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).**

```tsx
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).**

```tsx
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).**

```tsx
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.**

```tsx
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.**

```tsx
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.**

```tsx
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.