L26. Print Root to Node Path in Binary Tree | C++ | Java

This chapter explores how to find and print the path from the root node to a specified target node in a binary tree. Because standard binary tree nodes typically only possess pointers pointing downwards to their left and right children (and lack parent pointers), finding this path requires a systematic recursive traversal coupled with smart backtracking.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given a Binary Tree and a target node value (e.g., searching for node 7), our objective is to return the exact sequence of node values starting from the root down to the target (e.g., 1 -> 2 -> 5 -> 7).

The Parent Pointer Contrast:

• With Parent Pointers (Trivial Case): If every node stored a reference to its parent, you could start directly at the target node (7), hop to its parent (5), then to (2), and finally to (1), stopping when you hit null.
• Without Parent Pointers (Standard Binary Tree): Standard trees only provide top-down navigation (root -> children). To solve this efficiently, we must explore paths from the top down while keeping track of our current path history, gracefully retreating (backtracking) whenever we hit a dead end.

2. Core Mental Model & Backtracking Strategy

The solution relies on Recursion combined with Backtracking and a single shared data structure (such as an array or vector passed by reference).

Real-Life Analogy: Exploring a Maze

Imagine you are exploring a maze with a spool of thread and a marker. Every time you step into a room, you write down the room's name in your notebook and walk forward.

• If you reach a dead end or a room that does not contain your target, you must turn around and erase the room's name from your notebook before stepping back out.
• If you finally step into the room containing your treasure (the target), you stop erasing and shout "True!", freezing your notebook as the exact winning path.

3. Step-by-Step Tree Walkthrough

Let trace how the algorithm processes the tree when searching for target 7:

1. Start at Root 1:

   • Add 1 to the path array: [1]
   • Check if 1 == 7? No.
   • Explore Left Child (2).

2. At Node 2:

   • Add 2 to the path array: [1, 2]
   • Check if 2 == 7? No.
   • Explore Left Child (4).

3. At Node 4:

   • Add 4 to the path array: [1, 2, 4]
   • Check if 4 == 7? No.
   • Explore Left (null -> returns false) and Right (null -> returns false).
   • Backtrack: Neither child has 7. Remove 4 from the array. Array is now [1, 2]. Return false.

4. Back at Node 2 (trying Right Child 5):

   • Explore Right Child (5).
   • Add 5 to the path array: [1, 2, 5]
   • Check if 5 == 7? No.
   • Explore Left Child (6): returns false (and backtracks 6 from array).
   • Explore Right Child (7):
     • Add 7 to the path array: [1, 2, 5, 7]
     • Check if 7 == 7? Match found!
     • Return true without removing 7.

5. Propagation of Success:

   • Node 5 receives true from its right call -> returns true (retaining [1, 2, 5, 7]).
   • Node 2 receives true -> returns true.
   • Root 1 receives true -> terminates search. Final path is locked: [1, 2, 5, 7].

4. Naive vs. Optimal Recursive Approach

5. Implementation Code (C++ & Java)

C++ Implementation

#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    bool getPath(TreeNode* root, vector<int>& arr, int target) {
        // Base case: if root is null, path doesn't exist here
        if (root == nullptr) {
            return false;
        }
        
        // 1. Push current node into the path vector
        arr.push_back(root->val);
        
        // 2. Check if current node is the target
        if (root->val == target) {
            return true;
        }
        
        // 3. Recursively search left and right subtrees
        if (getPath(root->left, arr, target) || getPath(root->right, arr, target)) {
            return true;
        }
        
        // 4. Backtrack: if neither branch contained target, remove node and return false
        arr.pop_back();
        return false;
    }

public:
    vector<int> solve(TreeNode* root, int b) {
        vector<int> arr;
        if (root == nullptr) {
            return arr;
        }
        getPath(root, arr, b);
        return arr;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private boolean getPath(TreeNode root, List<int> arr, int target) {
        // Base case: if root is null, return false
        if (root == null) {
            return false;
        }
        
        // 1. Add current node to path list
        arr.add(root.val);
        
        // 2. Check if target is reached
        if (root.val == target) {
            return true;
        }
        
        // 3. Recurse down left or right subtrees
        if (getPath(root.left, arr, target) || getPath(root.right, arr, target)) {
            return true;
        }
        
        // 4. Backtrack: remove last element if path fails
        arr.remove(arr.size() - 1);
        return false;
    }

    public List<Integer> solve(TreeNode root, int b) {
        List<Integer> arr = new ArrayList<>();
        if (root == null) {
            return arr;
        }
        getPath(root, arr, b);
        return arr;
    }
}

6. Complete Flow Walkthrough (Code Execution)

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the total number of nodes in the binary tree. In the worst-case scenario, we may need to visit every node once if the target is located at the deepest leaf or doesn't exist.
• Space Complexity: $\mathcal{O}(H)$, where $H$ is the height of the binary tree. This accounts for the recursive call stack space during traversal, as well as the auxiliary space used by the path vector/array. In a skewed tree, this is $\mathcal{O}(N)$; in a balanced tree, it is $\mathcal{O}(\log N)$.

Summary and Key Takeaways

• - Absence of Parent Pointers: Standard binary trees lack upward pointers, requiring a top-down recursive traversal to discover paths.
• - Backtracking Mechanism: Use a single shared data structure passed by reference, adding elements upon entering a node and removing (pop_back() / remove()) upon confirming a dead end.
• - Short-Circuiting Evaluation: Combine left and right recursive calls with logical OR (||). The moment one branch returns true, halt further exploration and bubble the success flag upward.
• - Preserving the Winning Path: When the target is successfully matched, return true immediately without executing the backtrack removal step, preserving the exact root-to-node sequence.
• - Time & Space Efficiency: Achieves optimal $\mathcal{O}(N)$ time complexity and $\mathcal{O}(H)$ auxiliary space complexity by avoiding redundant list cloning.