A tree having multiple children at any level , find the path between two nodes [closed]

Question

we have a tree having as many children at any level 2 nodes are given and we have to find the path between two node how can we do that ?

                1
      /         |        \
     2          3         4
    / \         |       /   \
   5   8       11      12    13
  /\                   |
 6  9                 14
 / \
7   10

We have to find path between node 7 and 14. The result should be:

7 -> 6 -> 5 -> 2 -> 1 -> 4 -> 12 -> 14

Answer 1

Lets say we want to find the path between nodes A and B.

A simple approach would be to find the lowest common ancestor (LCA) of the two nodes. The brute force approach would be to find the path from root to A and also from root to B (you could use breadth first or depth first traversal to do that) and store the paths in a list. Walk through the list to see the lowest common node, if there is none it would be the root itself. Now you have two partial paths from Node A to LCA and from Node B to LCA, concatenate the paths to get the path from A to B.

If the tree provides more features like parent pointer or level number per node etc, it can be done more efficiently. For example if parent pointer is present, you could start with the individual nodes moving up to root and stopping when they reach a common node.