Be the first user to complete this post
|
Add to List |
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
- Start from the root and compare it with x, if matched then we have found the node.
- Else go left and right.
- Recursively do steps 1 and 2 till you find the node x.
- Now when you have found the node, stop the recursion.
- Now while backtracking, 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]