Be the first user to complete this post
|
Add to List |
Print a path from Root to Node in Binary Tree
Objective: Given a Binary tree (Not binary Search Tree ), Print a path from root to a given node.
Input: A binary tree, a node x
Output: Path from root to a given node
Example :

Approach :
since it's not a binary search tree, we cannot use binary search technique to reach to the node. we need to travel all the nodes in order to find the node
- Start from the root and compare it with x, if matched then we have found the node.
- Else go left and right.
- Recursively do step 2 and 3 till you find the node x.
- Now when you have found the node, stop the recursion.
- Now while going back to the root while back tracking, store the node values in the ArrayList.
- Reverse the ArrayList and print it.
- see the picture below

Time Complexity : O(n)
Code:
Path [1, 2, 5, 8]
Also Read: