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
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)
Path [1, 2, 5, 8]
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.