Type like pro

# Find path of a node from root

## Problem

Given a binary tree and one of its nodes, find the path from root to the given node

## Solution

We solve this by recursion. We start from the root. If the current node is equal to the given node we add it to a list and return. In this way from any node we check the path returned by right and left children, any non null path contains the node.

## Code

import java.util.ArrayList;
import java.util.List;

public class FindPathFromRoot
{
public static void main(String[] args)
{
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
Node e = new Node(5);
Node f = new Node(6);
Node g = new Node(7);
Node h = new Node(8);
a.left = b;
a.right = c;
b.left = d;
c.left = e;
c.right = f;
f.left = g;
f.right = h;

List < node > path = findPath(a, e);
for (Node node : path)
System.out.println(node.value);
}

private static List < node > findPath(Node root, Node node)
{
if (root == null)
return null;

if (root == node)
{
List < node > path = new ArrayList < node >();
return path;
}
List < node > leftPath = findPath(root.left, node);
List < node > rightPath = findPath(root.right, node);
if (leftPath != null)
{
return leftPath;
}
if (rightPath != null)
{
return rightPath;
}
return null;
}

static class Node
{
Node left;
Node right;
int value;

public Node(int value)
{
this.value = value;
}
}
}