45. Print a path from Root to Node in Binary Tree

Objective: Given a Binary tree (Not a binary Search Tree ), Print a path from the root to a given node.

Example:

Approach :

since it's not a binary search tree, we cannot use a binary search technique to reach to the node. we need to travel all the nodes to find the node

1. Start from the root and compare it with x, if matched then we have found the node.
2. Else go left and right.
3. Recursively do steps 1 and 2 till you find the node x.
4. Now when you have found the node, stop the recursion.
5. Now while backtracking, store the node values in the ArrayList.
6. Reverse the ArrayList and print it.
7. see the picture below

Time Complexity : O(n)

Path [1, 2, 5, 8]

Related Problems:

- Graph – Find Cycle in Undirected Graph using Disjoint Set (Union-Find) Hard
- Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree). Hard
- Printing Nodes without Siblings in a Binary Tree Beginner
- Identifying Maximum Gain from Sequential Elements Medium
- Merge or Combine Two Sorted Linked Lists Medium