[AlgoMastery]
Topics›Tree›Search in Tree
📖

Search in Tree

Tree
~20 min read
5 practice problems

Search in Tree

Overview

Tree search problems involve finding specific nodes within a tree structure based on their values, properties, or relationships. These problems are fundamental in computer science and appear frequently in coding interviews, system design, and algorithmic challenges.

Key Search Patterns

1. Basic Node Search by Value

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

function searchNode(root, targetValue) {
    if (root === null) return null;
    
    if (root.val === targetValue) {
        return root;
    }
    
    // Search in left subtree
    const leftResult = searchNode(root.left, targetValue);
    if (leftResult !== null) return leftResult;
    
    // Search in right subtree
    const rightResult = searchNode(root.right, targetValue);
    return rightResult;
}

2. Search in Binary Search Tree (BST)

function searchInBST(root, targetValue) {
    if (root === null) return null;
    
    if (root.val === targetValue) {
        return root;
    }
    
    // In BST, we can leverage ordering property
    if (targetValue < root.val) {
        return searchInBST(root.left, targetValue);
    } else {
        return searchInBST(root.right, targetValue);
    }
}

Search Applications

1. Find Node by Value (Generic Tree)

function findNodeByValue(root, targetValue) {
    if (root === null) return null;
    
    // Check current node
    if (root.val === targetValue) {
        return root;
    }
    
    // Search in left subtree
    const leftResult = findNodeByValue(root.left, targetValue);
    if (leftResult !== null) return leftResult;
    
    // Search in right subtree
    const rightResult = findNodeByValue(root.right, targetValue);
    return rightResult;
}

2. Find Node by Property

function findNodeByProperty(root, propertyChecker) {
    if (root === null) return null;
    
    // Check current node against property
    if (propertyChecker(root)) {
        return root;
    }
    
    // Search in left subtree
    const leftResult = findNodeByProperty(root.left, propertyChecker);
    if (leftResult !== null) return leftResult;
    
    // Search in right subtree
    const rightResult = findNodeByProperty(root.right, propertyChecker);
    return rightResult;
}

// Example usage:
// Find first node with even value
const evenNode = findNodeByProperty(
    root, 
    node => node.val % 2 === 0
);

3. Search in Complete Tree

function searchCompleteTree(root, targetValue) {
    if (root === null) return null;
    
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node.val === targetValue) {
            return node;
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return null; // Not found
}

Search in Binary Search Tree

BST Search Implementation

function searchBST(root, targetValue) {
    if (root === null) return null;
    
    // BST property: left subtree < root < right subtree
    if (targetValue === root.val) {
        return root;
    }
    
    if (targetValue < root.val) {
        // Search in left subtree
        return searchBST(root.left, targetValue);
    } else {
        // Search in right subtree
        return searchBST(root.right, targetValue);
    }
}

// Iterative approach for BST search
function searchBSTIterative(root, targetValue) {
    let current = root;
    
    while (current !== null) {
        if (targetValue === current.val) {
            return current;
        }
        
        if (targetValue < current.val) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    
    return null; // Not found
}

BST Search with Path Tracking

function searchBSTWithPath(root, targetValue) {
    const path = [];
    
    function search(node) {
        if (node === null) return null;
        
        path.push(node.val);
        
        if (targetValue === node.val) {
            return node;
        }
        
        if (targetValue < node.val) {
            return search(node.left);
        } else {
            return search(node.right);
        }
    }
    
    const result = search(root);
    return {
        found: result !== null,
        path: path,
        node: result
    };
}

Advanced Search Patterns

1. Find All Nodes with Value

function findAllNodesWithValue(root, targetValue) {
    const results = [];
    
    function dfs(node) {
        if (node === null) return;
        
        if (node.val === targetValue) {
            results.push(node);
        }
        
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return results;
}

2. Find Nodes Within Range (BST)

function findNodesInRange(root, min, max) {
    const results = [];
    
    function dfs(node) {
        if (node === null) return;
        
        // Check if current node is in range
        if (node.val >= min && node.val <= max) {
            results.push(node.val);
        }
        
        // If current value is greater than min, search left subtree
        if (node.val > min) {
            dfs(node.left);
        }
        
        // If current value is less than max, search right subtree
        if (node.val < max) {
            dfs(node.right);
        }
    }
    
    dfs(root);
    return results;
}

3. Find Nodes by Depth

function findNodesAtDepth(root, targetDepth) {
    const results = [];
    
    function dfs(node, currentDepth) {
        if (node === null) return;
        
        if (currentDepth === targetDepth) {
            results.push(node);
            return;
        }
        
        dfs(node.left, currentDepth + 1);
        dfs(node.right, currentDepth + 1);
    }
    
    dfs(root, 0);
    return results;
}

4. Find Nodes by Level Order

function findNodesByLevel(root, targetLevel) {
    if (root === null || targetLevel < 0) return [];
    
    const queue = [root];
    let currentLevel = 0;
    
    while (queue.length > 0 && currentLevel < targetLevel) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        currentLevel++;
    }
    
    return queue; // All nodes at target level
}

Search with Additional Properties

1. Find Node by Multiple Conditions

function findNodeByMultipleConditions(root, conditions) {
    function checkConditions(node) {
        return Object.keys(conditions).every(key => {
            if (typeof conditions[key] === 'function') {
                return conditions[key](node);
            }
            return node[key] === conditions[key];
        });
    }
    
    function search(node) {
        if (node === null) return null;
        
        if (checkConditions(node)) {
            return node;
        }
        
        const leftResult = search(node.left);
        if (leftResult !== null) return leftResult;
        
        return search(node.right);
    }
    
    return search(root);
}

// Example usage:
const node = findNodeByMultipleConditions(
    root,
    {
        val: 5, // Value must be 5
        isLeaf: node => !node.left && !node.right // Must be leaf node
    }
);

2. Find Node with Custom Comparison

function searchWithCustomComparator(root, targetValue, comparator) {
    function search(node) {
        if (node === null) return null;
        
        // Use custom comparator function
        if (comparator(node.val, targetValue)) {
            return node;
        }
        
        const leftResult = search(node.left);
        if (leftResult !== null) return leftResult;
        
        return search(node.right);
    }
    
    return search(root);
}

// Example: Find node where value is greater than target
const greaterNode = searchWithCustomComparator(
    root, 
    10,
    (val, target) => val > target
);

Time and Space Complexity

| Search Method | Time Complexity | Space Complexity |

|-------------|---------------|----------------|

| Generic Tree Search | O(n) | O(h) |

| BST Search | O(log n) avg, O(n) worst | O(h) |

| Iterative BST Search | O(log n) avg, O(n) worst | O(1) |

| Level-order Search | O(n) | O(w) |

Where:

  • n = number of nodes in tree
  • h = height of tree (recursion stack space)
  • w = maximum width of tree (queue space)

Common Variations

1. Search with Path Tracking

function searchWithPath(root, targetValue) {
    const path = [];
    
    function search(node) {
        if (node === null) return null;
        
        path.push(node.val);
        
        if (node.val === targetValue) {
            return node;
        }
        
        const leftResult = search(node.left);
        if (leftResult !== null) return leftResult;
        
        const rightResult = search(node.right);
        if (rightResult !== null) return rightResult;
        
        // Backtrack - remove from path
        path.pop();
        return null;
    }
    
    const result = search(root);
    return {
        found: result !== null,
        path: [...path],
        node: result
    };
}

2. Search with Duplicate Handling

function searchWithDuplicates(root, targetValue) {
    const results = [];
    
    function dfs(node) {
        if (node === null) return;
        
        if (node.val === targetValue) {
            results.push(node);
        }
        
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return results;
}

3. Search with Early Termination

function searchWithEarlyTermination(root, targetValue, maxDepth = Infinity) {
    function search(node, currentDepth) {
        if (node === null || currentDepth > maxDepth) return null;
        
        if (node.val === targetValue) {
            return node;
        }
        
        const leftResult = search(node.left, currentDepth + 1);
        if (leftResult !== null) return leftResult;
        
        return search(node.right, currentDepth + 1);
    }
    
    return search(root, 0);
}

Common Mistakes to Avoid

1. Incorrect Base Case Handling

// ❌ Wrong - Not properly handling null nodes
function wrongSearch(root, target) {
    if (root.val === target) return root;
    
    // Missing null check - will throw error
    const left = search(root.left, target);
    return search(root.right, target);
}

2. Missing Return Values

// ❌ Wrong - Not returning found nodes properly
function incompleteSearch(root, target) {
    if (root === null) return;
    
    if (root.val === target) {
        // Missing return statement
        return root; // This is never reached in actual code flow
    }
    
    search(root.left, target);
    search(root.right, target);
}

3. BST Property Misunderstanding

// ❌ Wrong - Not leveraging BST properties
function wrongBSTSearch(root, target) {
    // This is generic tree search, not BST optimized
    if (root === null) return null;
    
    if (root.val === target) return root;
    
    // This doesn't use BST ordering
    const left = search(root.left, target);
    const right = search(root.right, target);
    
    return left || right;
}

Real-World Applications

1. Database Indexing

// BST-based indexing for fast lookups
class DatabaseIndex {
    constructor() {
        this.indexTree = null;
    }
    
    searchByValue(value) {
        return searchInBST(this.indexTree, value);
    }
    
    searchByRange(min, max) {
        return findNodesInRange(this.indexTree, min, max);
    }
}

2. File System Navigation

// Tree structure for directory navigation
class FileSystemTree {
    constructor() {
        this.root = null;
    }
    
    findFile(path) {
        // Search for file by path in tree structure
        return this.searchPath(this.root, path);
    }
    
    searchByProperty(property, value) {
        return findNodeByProperty(this.root, node => 
            node[property] === value
        );
    }
}

3. Configuration Management

// Tree-based configuration system
class ConfigTree {
    constructor() {
        this.configTree = null;
    }
    
    findSetting(key) {
        return searchNode(this.configTree, key);
    }
    
    findSettingsByType(type) {
        return findNodeByProperty(this.configTree, node => 
            node.type === type
        );
    }
}

Performance Optimization Tips

1. Early Termination

function optimizedSearch(root, target) {
    // For BST, use iterative approach to avoid stack overflow
    let current = root;
    
    while (current !== null) {
        if (current.val === target) {
            return current;
        }
        
        if (target < current.val) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    
    return null;
}

2. Cache Search Results

class CachedSearchTree {
    constructor() {
        this.root = null;
        this.searchCache = new Map();
    }
    
    searchWithCaching(root, target) {
        const cacheKey = `${target}-${Date.now()}`;
        
        if (this.searchCache.has(cacheKey)) {
            return this.searchCache.get(cacheKey);
        }
        
        const result = searchInBST(root, target);
        this.searchCache.set(cacheKey, result);
        
        return result;
    }
}

3. Batch Search Operations

function batchSearch(root, targets) {
    const results = {};
    
    function search(node, targetValue) {
        if (node === null) return null;
        
        if (node.val === targetValue) {
            return node;
        }
        
        const leftResult = search(node.left, targetValue);
        if (leftResult !== null) return leftResult;
        
        return search(node.right, targetValue);
    }
    
    targets.forEach(target => {
        results[target] = search(root, target);
    });
    
    return results;
}

Common Interview Questions

1. Basic BST Search

function searchBST(root, target) {
    if (root === null) return null;
    
    if (root.val === target) return root;
    
    if (target < root.val) {
        return searchBST(root.left, target);
    } else {
        return searchBST(root.right, target);
    }
}

2. Find All Nodes with Value

function findAllNodes(root, target) {
    const results = [];
    
    function dfs(node) {
        if (node === null) return;
        
        if (node.val === target) {
            results.push(node);
        }
        
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return results;
}

3. Search with Path Information

function searchWithPath(root, target) {
    const path = [];
    
    function dfs(node) {
        if (node === null) return null;
        
        path.push(node.val);
        
        if (node.val === target) {
            return node;
        }
        
        const leftResult = dfs(node.left);
        if (leftResult !== null) return leftResult;
        
        const rightResult = dfs(node.right);
        if (rightResult !== null) return rightResult;
        
        path.pop(); // Backtrack
        return null;
    }
    
    const result = dfs(root);
    return {
        found: result !== null,
        path: [...path],
        node: result
    };
}

Best Practices

1. Consistent Return Values

Always return consistent types (node objects or null) for search operations.

2. Proper Error Handling

Handle edge cases like empty trees and missing nodes gracefully.

3. Leverage Tree Properties

Use BST ordering properties for optimized search in BSTs.

4. Memory Efficiency

Consider iterative approaches for deep trees to avoid stack overflow.

Key Takeaways

  1. Search is Fundamental: Essential for tree traversal and data retrieval operations
  2. BST Optimization: Leverage ordering properties for O(log n) search in balanced trees
  3. Multiple Approaches: Different search strategies for different use cases (recursive vs iterative)
  4. Real-World Applications: Database indexing, file systems, configuration management
  5. Performance Considerations: Balance between search speed and memory usage

Tree search operations form the backbone of many algorithms and systems where structured data needs to be efficiently located and accessed.

← PreviousSerialize and DeserializeNext →Search in Tree