Algorithms - 17. Tree Maze - Path Finding with Obstacles

When to use Tree Maze Algorithm

Use Tree Maze when you need to find valid paths through a tree structure with obstacles or constraints. While most commonly used for binary tree navigation with blocked nodes, it can be adapted for:

• Path finding with obstacles (classic use case - nodes with value 0 are blocked)
• Resource collection paths (collect items while avoiding hazards)
• Decision tree validation (find valid decision sequences)
• Game tree exploration (find winning paths avoiding losing positions)
• Directory traversal with permission checks (navigate file systems with access controls)
• Network routing through hierarchical structures (find paths avoiding failed nodes)
• Any problem where you need to find paths through a tree while respecting node-level constraints

Example problem

Corporate Hierarchy Navigation: In a company org chart represented as a binary tree, each node has a value (1 = active employee, 0 = vacant position). Find if there's a valid chain of command from the CEO (root) to any front-line employee (leaf), and track the complete reporting chain.

        CEO(1)
       /      \
    VP1(1)    VP2(0)     <- VP2 position vacant (blocked)
    /    \      /  \
  Mgr1(1) Mgr2(0) X  X   <- Can't reach through VP2
   /  \    /  \
 Emp1 Emp2 X  X          <- Can't reach through Mgr2

After processing the tree:

• Valid path exists: CEO → VP1 → Mgr1 → Emp1
• Complete chain: [CEO, VP1, Mgr1, Emp1]
• VP2's entire subtree is unreachable due to vacant position

Answer: Yes, there's a valid chain of command from CEO to front-line employees, avoiding all vacant positions.

What Tree Maze Actually Does

Tree Maze algorithm navigates a binary tree from root to leaves while avoiding obstacle nodes. It provides two core operations:

1. REACHABILITY CHECK: Determine if any valid path exists from root to a leaf
2. PATH TRACKING: Record the complete path taken to reach a leaf

Think of it like navigating a maze where:

• Nodes are rooms: Each tree node is a room you can enter
• Value 0 = locked door: Can't pass through these nodes
• Leaves are exits: Reaching any leaf means finding an exit
• Path = route taken: Track which rooms you passed through

How the Navigation Works

Reachability Check - "Can I reach any exit?"

When checking if a path exists, the algorithm:

1. Starts at the root (entrance)
2. Checks if current node is blocked (value 0)
3. If at a leaf (no children) - success, found an exit!
4. Otherwise, tries left path first
5. If left fails, tries right path
6. Returns true if either path succeeds

Path Tracking - "Show me the route"

When tracking the actual path, it:

1. Maintains a path array as it explores
2. Adds current node value when entering
3. If reaches a leaf - path is complete
4. If dead end - removes node from path (backtracking)
5. Continues until finding a valid path or exhausting options

When These Operations Happen

The navigation only explores paths when you explicitly call the functions:

const tree = new TreeNode(1);
tree.left = new TreeNode(1);
tree.right = new TreeNode(0); // Blocked path

// Check if ANY path to a leaf exists
const pathExists = canReachLeaf(tree); // Returns true (via left)

// Get the actual path taken
const path = [];
findLeafPath(tree, path); // Fills path with [1, 1]

The beauty is that DFS naturally handles backtracking - when hitting a blocked node or dead end, it automatically returns to try alternative paths!

Single most important insight

Trees are naturally recursive structures where each subtree is an independent maze - and by checking if current node is passable first, then recursively exploring children, we ensure we never venture into blocked paths while exhaustively trying all valid routes.

Mental note: The algorithm's genius lies in the order of checks: "Am I blocked? Am I at the exit? Can I go left? Can I go right?" This simple sequence, combined with automatic backtracking when returning false, explores all possible paths without getting stuck in blocked areas.

Decision Framework

The algorithm makes decisions at three key points:

Entry Decision - "Can I enter this room?"

• If node is null or has value 0: blocked, turn back
• Otherwise: proceed to explore

Exit Decision - "Am I at the exit?"

• If node has no children (leaf): success, found exit
• Otherwise: must continue searching

Direction Decision - "Which way should I try?"

• Always try left subtree first (arbitrary but consistent)
• If left succeeds: done, don't need to check right
• If left fails: try right subtree
• If both fail: backtrack (this path is a dead end)

Code

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// === REACHABILITY CHECK - Can we reach any leaf? ===
function canReachLeaf(currentNode) {
  // Extract node properties for clarity
  const nodeExists = currentNode != null;
  const nodeValue = nodeExists ? currentNode.val : null;

  // DECISION FRAMEWORK: Can I enter this room?
  const isNodeBlocked = nodeValue === 0;
  const cannotEnter = !nodeExists || isNodeBlocked;

  if (cannotEnter) {
    // Why: We hit a wall (null) or locked door (0)
    // This path is impossible, try another
    return false;
  }

  // Check if we've reached our destination
  const hasNoLeftChild = currentNode.left == null;
  const hasNoRightChild = currentNode.right == null;
  const isLeafNode = hasNoLeftChild && hasNoRightChild;

  // DECISION FRAMEWORK: Am I at the exit?
  if (isLeafNode) {
    // Why: Leaves are our exits - we found a way out!
    return true;
  }

  // DECISION FRAMEWORK: Which way should I try?
  // Try left path first (arbitrary choice, but consistent)
  const leftPathExists = canReachLeaf(currentNode.left);

  if (leftPathExists) {
    // Why: Left path found an exit, no need to explore right
    return true;
  }

  // Left failed, now try right path
  const rightPathExists = canReachLeaf(currentNode.right);

  if (rightPathExists) {
    // Why: Right path found an exit
    return true;
  }

  // Why: Both children failed to find exits
  // This node is a dead end in our maze
  return false;
}

// === PATH TRACKING - Record the actual path to a leaf ===
function findLeafPath(currentNode, pathTaken) {
  // Extract node properties for clarity
  const nodeExists = currentNode != null;
  const nodeValue = nodeExists ? currentNode.val : null;

  // DECISION FRAMEWORK: Can I enter this room?
  const isNodeBlocked = nodeValue === 0;
  const cannotEnter = !nodeExists || isNodeBlocked;

  if (cannotEnter) {
    // Why: Can't build a path through walls or locked doors
    return false;
  }

  // Optimistically add this node to our journey
  // Why: We assume this node is part of the solution path
  pathTaken.push(nodeValue);

  // Check if we've reached our destination
  const hasNoLeftChild = currentNode.left == null;
  const hasNoRightChild = currentNode.right == null;
  const isLeafNode = hasNoLeftChild && hasNoRightChild;

  // DECISION FRAMEWORK: Am I at the exit?
  if (isLeafNode) {
    // Why: We found a complete path from root to leaf!
    // Keep everything in pathTaken
    return true;
  }

  // DECISION FRAMEWORK: Which way should I try?
  // Explore left subtree first
  const leftPathSucceeded = findLeafPath(currentNode.left, pathTaken);

  if (leftPathSucceeded) {
    // Why: Left path reached a leaf, our path is complete
    // The path array already contains the full route
    return true;
  }

  // Left didn't work, try right subtree
  const rightPathSucceeded = findLeafPath(currentNode.right, pathTaken);

  if (rightPathSucceeded) {
    // Why: Right path reached a leaf, our path is complete
    return true;
  }

  // DECISION FRAMEWORK: Backtrack - this room led nowhere
  // Why: Neither child led to a leaf, so this node isn't
  // part of any valid path. Remove it before trying elsewhere
  pathTaken.pop();
  return false;
}

// === EXAMPLE USAGE: Corporate Hierarchy ===
// Building the tree from our example
const ceo = new TreeNode(1); // CEO (active)
const vp1 = new TreeNode(1); // VP1 (active)
const vp2 = new TreeNode(0); // VP2 (vacant/blocked)
const mgr1 = new TreeNode(1); // Manager 1 (active)
const mgr2 = new TreeNode(0); // Manager 2 (vacant/blocked)
const emp1 = new TreeNode(1); // Employee 1 (active)
const emp2 = new TreeNode(1); // Employee 2 (active)

// Construct the hierarchy
ceo.left = vp1;
ceo.right = vp2;
vp1.left = mgr1;
vp1.right = mgr2;
vp2.left = null; // No one under vacant VP2
vp2.right = null;
mgr1.left = emp1;
mgr1.right = emp2;
mgr2.left = null; // No one under vacant Mgr2
mgr2.right = null;

// Check if there's any valid chain of command
console.log("Valid chain exists?", canReachLeaf(ceo)); // true

// Find the actual chain of command
const commandChain = [];
findLeafPath(ceo, commandChain);
console.log("Chain of command:", commandChain); // [1, 1, 1, 1]
// This represents: CEO → VP1 → Mgr1 → Emp1

// What if we check from VP2's subtree?
console.log("Path from VP2?", canReachLeaf(vp2)); // false (VP2 is blocked)

// What about checking from Mgr1?
const fromManager = [];
findLeafPath(mgr1, fromManager);
console.log("Path from Mgr1:", fromManager); // [1, 1] (Mgr1 → Emp1)

// === ADVANCED EXAMPLE: Multiple Paths ===
// Tree with multiple valid paths to leaves
const mazeRoot = new TreeNode(1);
const left = new TreeNode(1);
const right = new TreeNode(1);
const leftLeft = new TreeNode(0); // Blocked!
const leftRight = new TreeNode(1); // Valid leaf
const rightLeft = new TreeNode(1); // Valid leaf
const rightRight = new TreeNode(0); // Blocked!

mazeRoot.left = left;
mazeRoot.right = right;
left.left = leftLeft;
left.right = leftRight;
right.left = rightLeft;
right.right = rightRight;

// Even with blocked nodes, we can find a path
const mazePath = [];
findLeafPath(mazeRoot, mazePath);
console.log("Path through maze:", mazePath); // [1, 1, 1]
// Found the first valid path: Root → Left → LeftRight

// === HELPER: Find ALL valid paths (not just first) ===
function findAllValidPaths(currentNode, currentPath = [], allPaths = []) {
  // Check if we can enter this node
  const nodeExists = currentNode != null;
  const nodeValue = nodeExists ? currentNode.val : null;
  const isBlocked = nodeValue === 0;

  if (!nodeExists || isBlocked) {
    // Why: Can't traverse through this node
    return allPaths;
  }

  // Add current node to the path we're building
  currentPath.push(nodeValue);

  // Check if we've reached a leaf
  const hasNoChildren = currentNode.left == null && currentNode.right == null;

  if (hasNoChildren) {
    // Why: Found a complete root-to-leaf path
    // Save a copy since we'll modify currentPath later
    const completePath = [...currentPath];
    allPaths.push(completePath);
  } else {
    // Why: Not at a leaf yet, explore all possible routes
    // Unlike findLeafPath, we explore BOTH paths always
    findAllValidPaths(currentNode.left, currentPath, allPaths);
    findAllValidPaths(currentNode.right, currentPath, allPaths);
  }

  // Backtrack: Remove current node before returning
  // Why: currentPath is reused for exploring other branches
  currentPath.pop();
  return allPaths;
}

const allValidPaths = findAllValidPaths(mazeRoot);
console.log("All valid paths:", allValidPaths);
// [[1, 1, 1], [1, 1, 1]]  (two valid paths exist)

Doubt buster

Common doubt: "Why doesn't the algorithm get stuck exploring infinite branches or going in circles? How does it know when to give up on a path?"

This is a natural concern when thinking about maze navigation - in physical mazes, you might wander in circles or get lost in dead ends. Let's see why this can't happen in tree traversal.

Why you might worry about getting stuck

In a general graph or a physical maze:

    A ←→ B
    ↑    ↓
    D ←→ C

You could go A → B → C → D → A → B... forever in circles!

Why trees are different

Trees have a crucial property: no cycles. Once you go down a path, you can never loop back to where you were:

       1
      / \
     2   3
    / \
   4   5

From 1 → 2 → 4, there's NO path back to 1 or 2
You either reach a leaf (4) or run out of children

The automatic "giving up" mechanism

The algorithm naturally stops exploring because of three guarantees:

1. Trees are finite structures

function canReachLeaf(root) {
  // Base case 1: Null node - physically nothing more to explore
  if (root == null) return false;

  // Base case 2: Blocked node - chosen to stop here
  if (root.val === 0) return false;

  // Base case 3: Leaf found - successful termination
  if (root.left == null && root.right == null) return true;

  // Recursive calls - but tree height is finite!
  return canReachLeaf(root.left) || canReachLeaf(root.right);
}

2. Each recursive call goes deeper (can't go sideways or up)

Call stack for tree:    1
                       / \
                      2   0
                     /
                    3

canReachLeaf(1) - depth 0
  ├── canReachLeaf(2) - depth 1
  │   ├── canReachLeaf(3) - depth 2
  │   │   └── returns true (leaf!)
  │   └── returns true
  ├── returns true (don't need to check right)

3. The call stack naturally handles backtracking

When a path fails, the function returns and the previous call continues:

// When we hit a dead end at node 5:
canReachLeaf(5) returns false
// We're automatically back at node 2's context:
if (canReachLeaf(node5)) { /* skipped */ }
if (canReachLeaf(node6)) { /* tries next */ }

Concrete example: Why we can't get stuck

Consider this tree with a blocked node:

       1
      / \
     2   0  ← blocked
    / \
   3   4

Trace of execution:

1. canReachLeaf(1): Not blocked, not a leaf, check children
2. canReachLeaf(2): Not blocked, not a leaf, check children
3. canReachLeaf(3): Not blocked, IS a leaf → return true
4. Back to step 2: left child returned true → return true
5. Back to step 1: left child returned true → return true
6. Never even check the right (blocked) path!

Why the path array doesn't grow infinitely

The path array in findLeafPath is self-managing:

path.push(root.val);        // Add when entering

if (/* found leaf */) {
  return true;              // Keep the path
}

if (/* no valid path */) {
  path.pop();              // Remove when backtracking
  return false;
}

Maximum path length = tree height (not infinite!)

For a tree of height h:

• Worst case: path grows to size h
• When backtracking: path shrinks
• Final path: exactly root-to-leaf distance

The beauty of tree recursion

The algorithm can't get stuck because:

1. No cycles - Can't revisit nodes (tree property)
2. Finite depth - Eventually hit leaves or nulls
3. Automatic backtracking - Call stack handles returning
4. Clear termination - Three explicit base cases
5. Progress guaranteed - Each recursive call goes deeper

The tree structure itself prevents the problems you might encounter in general maze solving. The algorithm doesn't need to track visited nodes or worry about cycles - the tree topology handles all of that automatically!