Search Word in Root-to-Leaf Word Tree

Problem

We are given a rooted binary tree whose nodes store single characters. Every root → leaf path spells a complete word (each leaf terminates exactly one word). Given a target word W, determine whether the tree contains W as one of those root-to-leaf paths.

We contrast:

1. A brute-force DFS that enumerates all root→leaf words and compares each to W.
2. A pruned backtracking DFS that aborts a branch immediately upon character mismatch at some depth.

Unlike a trie (multi-way branching keyed by character), here each node has at most two children (left, right), so pruning cannot pick a unique next child by character; it only stops early when mismatch occurs.

Examples

Example 1

graph TD;
	A(A):::green --- N(N) & I(I):::green
	N --- T(T) & D(D)
	I --- M(M):::green & R(R)
	
	T ~~~ W1["ANT"]
	D ~~~ W2["AND"]
	M ~~~ W3["AIM"]:::green
	R ~~~ W4["AIR"]

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Input: root = [A, N, I, T, D, M, R], word = AIM
Output: true
Explanation: Root→A→I→M path exists and ends at a leaf.

Example 2

Input: root = [A, N, I, T, D, M, R], word = ARC
Output: false
Explanation: After A→R node, subtree does not contain a C completing a leaf word ARC.

Solution

Method 1 - Brute Force Enumeration

Intuition

Traverse every root→leaf path, build the word string, and compare with the target. Return true if any matches; otherwise false after full traversal.

Approach

1. Perform DFS from root; maintain path characters in a buffer.
2. When a node is a leaf (both children null), the buffer forms a full word.
3. Compare with target; if equal → return true / set flag.
4. Otherwise explore left then right.
5. After recursion, pop the character (backtracking) and continue; return false if no leaf word matches.

Visualization

graph LR;
	subgraph S1[" "]
		A(A):::orange--- N(N):::orange & I(I)
		N --- T(T):::orange & D(D)
		I --- M(M) & R(R)
		
		T ~~~ W1["ANT != AIM"]:::orange
		D ~~~ W2["AND"]
		M ~~~ W3["AIM"]
		R ~~~ W4["AIR"]
	end
	
	subgraph S2[" "]
		A2(A):::orange--- N2(N):::orange & I2(I)
		N2 --- T2(T) & D2(D):::orange
		I2 --- M2(M) & R2(R)
		
		T2 ~~~ W12["ANT"]
		D2 ~~~ W22["AND != AIM"]:::orange
		M2 ~~~ W32["AIM"]
		R2 ~~~ W42["AIR"]
	end	

	subgraph S3[" "]
		A3(A):::green--- N3(N) & I3(I):::green
		N3 --- T3(T) & D3(D)
		I3 --- M3(M):::green & R3(R)
		
		T3 ~~~ W13["ANT"]
		D3 ~~~ W23["AND"]
		M3 ~~~ W33["AIM == AIM"]:::green
		R3 ~~~ W43["AIR"]
	end	
S1 ~~~ S2 ~~~ S3
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
classDef orange fill:#FFA07A,stroke:#333,stroke-width:2px;	

Pseudocode

function brute(root, target):
  found = false
  path = []
  def dfs(node):
    if node is null or found: return
    path.append(node.char)
    if node.left is null and node.right is null:  # leaf
      if join(path) == target: found = true
    dfs(node.left)
    dfs(node.right)
    path.pop()
  dfs(root)
  return found

Code

C++

#include <string>
using namespace std;

struct Node {
	char ch;
	Node* left;
	Node* right;
	Node(char c) : ch(c), left(nullptr), right(nullptr) {}
};

class Solution {
public:
	bool searchWordBrute(Node* root, const string& target) {
		if (!root) return false;
		bool found = false;
		string path;
		dfs(root, target, path, found);
		return found;
	}
private:
	void dfs(Node* node, const string& target, string& path, bool& found) {
		if (!node || found) return;
		path.push_back(node->ch);
		if (!node->left && !node->right) { // leaf
			if (path == target) found = true;
		}
		dfs(node->left, target, path, found);
		dfs(node->right, target, path, found);
		path.pop_back();
	}
};

Java

class Node {
	char ch;
	Node left, right;
	Node(char c) { this.ch = c; }
}

class Solution {
	public boolean searchWordBrute(Node root, String target) {
		if (root == null) return false;
		StringBuilder path = new StringBuilder();
		boolean[] found = new boolean[1];
		dfs(root, target, path, found);
		return found[0];
	}
	private void dfs(Node node, String target, StringBuilder path, boolean[] found) {
		if (node == null || found[0]) return;
		path.append(node.ch);
		if (node.left == null && node.right == null) {
			if (path.toString().equals(target)) found[0] = true;
		}
		dfs(node.left, target, path, found);
		dfs(node.right, target, path, found);
		path.deleteCharAt(path.length() - 1);
	}
}

Python

from typing import Optional

class Node:
	def __init__(self, ch: str):
		self.ch = ch
		self.left: Optional['Node'] = None
		self.right: Optional['Node'] = None

class Solution:
	def searchWordBrute(self, root: Optional[Node], target: str) -> bool:
		if root is None:
			return False
		found = False
		path: list[str] = []

		def dfs(node: Optional[Node]):
			nonlocal found
			if node is None or found:
				return
			path.append(node.ch)
			if node.left is None and node.right is None:
				if ''.join(path) == target:
					found = True
			dfs(node.left)
			dfs(node.right)
			path.pop()

		dfs(root)
		return found

Complexity

• ⏰ Time complexity: O(T) – visits every node; T = total nodes (sum of all word lengths) in worst case.
• 🧺 Space complexity: O(L) – recursion/path stack length = height L (max word length).

Trade-offs

• Simple but wasteful: constructs and compares every word regardless of early mismatches.
• Cannot stop early on mismatching prefixes (other than after full leaf words).

Method 2 - Backtracking with Early Pruning

Intuition

Descend only as long as the current depth character matches the target at that position. If mismatch occurs, immediately backtrack—eliminating entire subtrees that cannot possibly yield the target word (pruning).

Approach

1. Maintain index i in target during DFS.
2. If node is null or node.ch != target[i] → prune (return False).
3. If i == len(target)-1, return True only if node is a leaf (no children).
4. Otherwise explore left and right children; return True if either succeeds.

Pseudocode

function pruned(root, target):
  if root is null or target == "": return false
  def dfs(node, i):
    if node is null: return false
    if node.char != target[i]: return false
    if i == len(target)-1:
      return node.left is null and node.right is null
    return dfs(node.left, i+1) or dfs(node.right, i+1)
  return dfs(root, 0)

Visualization

Pruned search halts at the node where the next letter would be N (not I), immediately backtracking and skipping the entire N subtree.

graph LR;
	subgraph S1[" "]
		A(A):::green--- N(N):::orange & I(I)
		N --- T(T) & D(D)
		I --- M(M) & R(R)
		
		N -.->|"backtrack as AN != AI"| A
		
		T ~~~ W1["ANT"]
		D ~~~ W2["AND"]
		M ~~~ W3["AIM"]
		R ~~~ W4["AIR"]
	end

	subgraph S3[" "]
		A3(A):::green--- N3(N) & I3(I):::green
		N3 --- T3(T) & D3(D)
		I3 --- M3(M):::green & R3(R)
		
		T3 ~~~ W13["ANT"]
		D3 ~~~ W23["AND"]
		M3 ~~~ W33["AIM"]:::green
		R3 ~~~ W43["AIR"]
	end	
S1 ~~~ S2 ~~~ S3
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
classDef orange fill:#FFA07A,stroke:#333,stroke-width:2px;	

Code

C++

class SolutionPruned {
public:
    bool searchWordPruned(Node* root, const string& target) {
        if (!root || target.empty()) return false;
        return dfs(root, target, 0);
    }
private:
    bool dfs(Node* node, const string& target, int i) {
        if (!node) return false;
        if (node->ch != target[i]) return false;
        if (i == (int)target.size() - 1)
            return !node->left && !node->right; // leaf check
        return dfs(node->left, target, i + 1) || dfs(node->right, target, i + 1);
    }
};

Java

class SolutionPruned {
    public boolean searchWordPruned(Node root, String target) {
        if (root == null || target.isEmpty()) return false;
        return dfs(root, target, 0);
    }
    private boolean dfs(Node node, String target, int i) {
        if (node == null) return false;
        if (node.ch != target.charAt(i)) return false;
        if (i == target.length() - 1)
            return node.left == null && node.right == null;
        return dfs(node.left, target, i + 1) || dfs(node.right, target, i + 1);
    }
}

Python

class SolutionPruned:
    def searchWordPruned(self, root: Optional[Node], target: str) -> bool:
        if root is None or not target:
            return False

        def dfs(node: Optional[Node], i: int) -> bool:
            if node is None:
                return False
            if node.ch != target[i]:
                return False
            if i == len(target) - 1:
                return node.left is None and node.right is None
            return dfs(node.left, i + 1) or dfs(node.right, i + 1)

        return dfs(root, 0)

Complexity

• ⏰ Time complexity: O(L) along successful path or early mismatch; worst-case O(T) if many nodes share the target prefix characters (must explore all).
• 🧺 Space complexity: O(L) – recursion depth equals path length.

Trade-offs

• Much faster in practice when branches diverge early.
• Slightly more logic; assumes children accessible by character (hash map) for O(1) next-step selection.

Summary

Backtracking here prunes binary tree branches immediately on character mismatch, illustrating the pruning principle: discard any subtree whose partial path can no longer match the target.