**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*

- 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)**

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.ArrayList; | |

import java.util.Collections; | |

public class PrintPathRootToNode { | |

public static ArrayList path; | |

public Boolean printPath(Node root, Node dest){ | |

if(root==null) return false; | |

if(root==dest||printPath(root.left,dest)||printPath(root.right,dest)){ | |

//System.out.print(" " + root.data); | |

path.add(root.data); | |

return true; | |

} | |

return false; | |

} | |

public static void main (String[] args) throws java.lang.Exception | |

{ | |

Node root = new Node(1); | |

root.left = new Node (2); | |

root.right = new Node (3); | |

Node n1 = new Node (4); | |

root.left.left = n1; | |

root.left.right = new Node (5); | |

Node n2 = new Node (8); | |

root.left.right.right = n2; | |

root.left.right.left = new Node (7); | |

PrintPathRootToNode i = new PrintPathRootToNode(); | |

path = new ArrayList(); | |

i.printPath(root,n2); | |

Collections.reverse(path); | |

System.out.println(" Path " + path); | |

} | |

} | |

class Node{ | |

int data; | |

Node left; | |

Node right; | |

public Node (int data){ | |

this.data = data; | |

left = null; | |

right = null; | |

} | |

} |

**Output**:

Path [1, 2, 5, 8]