Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Print a path from Root to Node in Binary Tree

Objec­tive: Given a Binary tree (Not binary Search Tree ), Print a path from root to a given node.

Input: A binary tree, a node x

Out­put: Path from root to a given node

Exam­ple :

path from root to Node example

path from root to Node example

Approach :

since it’s not a binary search tree, we can­not use binary search tech­nique to reach to the node. we need to travel all the nodes in order to find the node

  1. Start from the root and com­pare it with x, if matched then we have found the node.
  2. Else go left and right.
  3. Recur­sively 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 track­ing, store the node val­ues in the ArrayList.
  6. Reverse the ArrayList and print it.
  7. see the pic­ture below
Print path form root to Node

Print path form root to Node

Time Com­plex­ity : O(n)

Com­plete Code:


Out­put:

Path [1, 2, 5, 8]

You may also like...