Print path from root to a given node in a binary tree.
Given a Binary tree and a Key, Print a path from root to a key node.
Note: Given tree is Binary Tree and not Binary Search Tree.
Lets see sample input and output for better understanding:
 |
| Print path from root to given node in binary tree |
Algorithm
From Root to Key:
Step 1.
Do in-order traversal and check if the node is matching with the key?
If Yes, no need to further check further nodes and return true as indication that we found the node.
If No, collect the node as this node may be part of path from root to Key.
Step 2:
When the recursive function reverse back, if the result that is returned from recursive call is true either on left or right sub-tree, then current node will remain part of the path or else remove it from the path which we added initially assuming it may became part of the path.
Step 1:
Repeat the same step as above, but instead of adding the nodes in the path initially we will add it later when recursive call returns, so that node that are part of path is added in Reversed order.
Path from Matching Node to Root Path in a binary tree.
package com.javabypatel.binarytree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/*
Input: key = 5
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
From root to key: 1 -> 2 -> 5
From key to root: 5 -> 2-> 1
Input: key = 1
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
From root to key: 1
From key to root: 1
Input: key = 4
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
From root to key: 1 -> 2 -> 4
From key to root: 4 -> 2 -> 1
*/
public class PrintPathFromRoot {
private Node rootNode;
public static void main(String[] args) {
new PrintPathFromRoot();
}
public PrintPathFromRoot() {
addNodeInBinaryTree(rootNode, 1);
addNodeInBinaryTree(rootNode, 2);
addNodeInBinaryTree(rootNode, 3);
addNodeInBinaryTree(rootNode, 4);
addNodeInBinaryTree(rootNode, 5);
addNodeInBinaryTree(rootNode, 6);
addNodeInBinaryTree(rootNode, 7);
int key = 5;
Result res = getPathFromRoot(rootNode, key, new Result("", false));
System.out.println("Approach 1 result:");
if (res.isResult()) {
System.out.println(res.getPath());
} else {
System.out.println("No Path found");
}
List<Integer> path = new ArrayList<>();
getPathFromRoot(rootNode, key, path);
System.out.println("\nApproach 2 result:");
if (path.size() > 0) {
for (Integer i : path) {
System.out.print(i + " ");
}
} else {
System.out.println("No Path found");
}
path = new ArrayList<>();
getPathFromRoot(rootNode, key, path);
System.out.println("\nApproach 3 result:");
if (path.size() > 0) {
for (Integer i : path) {
System.out.print(i + " ");
}
} else {
System.out.println("No Path found");
}
path = new ArrayList<>();
getPathFromRootReverse(rootNode, key, path);
System.out.println("\nApproach 4 result:");
if (path.size() > 0) {
for (Integer i : path) {
System.out.print(i + " ");
}
} else {
System.out.println("No Path found");
}
}
private Result getPathFromRoot(Node rootNode, int key, Result result) {
if (rootNode == null) {
return result;
}
if (rootNode.getData() == key) {
return new Result(result.getPath() + " " + rootNode.getData(), true);
}
Result r = new Result(result.getPath() + " " + rootNode.getData(), false);
Result onLeft = getPathFromRoot(rootNode.getLeft(), key, r);
if (onLeft.isResult()) {
return onLeft;
}
Result onRight = getPathFromRoot(rootNode.getRight(), key, r);
if (onRight.isResult()) {
return onRight;
}
return onLeft.isResult() ? onLeft : onRight;
}
private boolean getPathFromRoot(Node rootNode, int key, List<Integer> path) {
if (rootNode == null) {
return false;
}
path.add(rootNode.getData());
if (rootNode.getData() == key) {
return true;
}
boolean onLeft = getPathFromRoot(rootNode.getLeft(), key, path);
if (onLeft) {
return onLeft;
}
boolean onRight = getPathFromRoot(rootNode.getRight(), key, path);
if (onRight) {
return onRight;
}
path.remove(path.size() - 1);
return false;
}
private boolean getPathFromRootReverse(Node rootNode, int key, List<Integer> path) {
if (rootNode == null) {
return false;
}
if (rootNode.getData() == key) {
path.add(rootNode.getData());
return true;
}
boolean onLeft = getPathFromRootReverse(rootNode.getLeft(), key, path);
boolean onRight = getPathFromRootReverse(rootNode.getRight(), key, path);
if (onLeft || onRight){
path.add(rootNode.getData());
}
return onLeft || onRight;
}
//Iterative way of adding new Node in Binary Tree.
private void addNodeInBinaryTree(Node rootNode, int data) {
if (rootNode == null) {
// No Nodes are Present, create one and assign it to rootNode
this.rootNode = new Node(data);
} else {
//Nodes present, So checking vacant position for adding new Node in sequential fashion
//Start scanning all Levels (level by level) of a tree one by one until we found a node whose either left or right node is null.
//For each and every node, we need to check whether Left and Right Node exist?
//If exist, then that node is not useful for adding new node but we need to store left and right node of that node for later processing
//that is why it is stored in Queue for sequential placement.
//If not exist, then we found a node, where new node will be placed but not sure on left or right, so check which side is null and place new node there.
Queue<Node> q = new LinkedList<Node>();
q.add(rootNode);
while (!q.isEmpty()) {
Node node = q.poll();
if (node.getLeft() != null && node.getRight() != null) {
q.add(node.getLeft());
q.add(node.getRight());
} else {
if (node.getLeft() == null) {
node.setLeft(new Node(data));
} else {
node.setRight(new Node(data));
}
break;
}
}
}
}
private void printTreeLevelOrder(Node rootNode) {
if (rootNode == null)
return;
Queue<Node> q = new LinkedList<Node>();
q.add(rootNode);
q.add(null);
while (!q.isEmpty()) {
Node node = q.poll();
if (node == null) {
if (q.peek() != null) {
System.out.println();
q.add(null);
continue;
} else {
break;
}
}
System.out.print(node.getData() + " ");
if (node.getLeft() != null)
q.add(node.getLeft());
if (node.getRight() != null)
q.add(node.getRight());
}
}
}
class Result {
private String path;
private boolean result;
public Result(String path, boolean result) {
this.path = path;
this.result = result;
}
public String getPath() {
return path;
}
public void setPath(String path) {
this.path = path;
}
public boolean isResult() {
return result;
}
public void setResult(boolean result) {
this.result = result;
}
}
Output:
Approach 1 result:
1 2 5
Approach 2 result:
1 2 5
Approach 3 result:
1 2 5
Approach 4 result:
5 2 1
You may also like to see
Sort Linked list using Merge sort
Bubble Sort
Heap Sort
Selection Sort
Insertion Sort
How ConcurrentHashMap works and ConcurrentHashMap interview questions
How Much Water Can A Bar Graph with different heights can Hold
Interview Questions-Answer Bank
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment