Be the first user to complete this post Login To Mark Completed

0

Add to List Add To List..(Max 5) Close Save

Medium

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

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 step 2 and 3 till you find the node x.
4. Now when you have found the node, stop the recursion.
5. Now while going back to the root while back tracking, store the node values in the ArrayList.
6. Reverse the ArrayList and print it.
7. see the picture below

Time Complexity : O(n)

Run This Code

Code:

Path [1, 2, 5, 8]

---

---

Also Read:

- Reverse a Linked List - Part 2 Medium
- Construct Binary Search Tree from a given Preorder Traversal using Recursion Hard
- Convert binary tree to its Sum tree Medium
- Print all subarrays using recursion Medium
- Collatz Conjecture - Steps to transform Number to 1 Beginner
- Generate All Strings of n bits. Medium
- Reverse a Linked List Beginner
- Graph – Depth First Search using Recursion Beginner

---