Binary Tree Ancestor Finder
Find ancestor of a node or in other words, we can say find a path between root and node.
Solution:
Recursive:
- Traverse tree in inorder and whenever found return true and call left child and right child recursively.
Non-Recursive:
- Traverse tree in BFS and store child parent map and use this map to render path, when item found.
Source Code:
Github: BinaryTreeAncestorFinder.java
Output:
1 / \ / \ / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 / / / / 8 6 \ 7 Recursive path for node 7: 7 => 6 => 5 => 2 => 1 => Non-Recursive path for node 7: 7 => 6 => 5 => 2 => 1 => Recursive path for node 3: 3 => 1 => Non-Recursive path for node 3: 3 => 1 =>