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 >();
   path.add(root);
   return path;
  }
  List < node > leftPath = findPath(root.left, node);
  List < node > rightPath = findPath(root.right, node);
  if (leftPath != null)
  {
   leftPath.add(0, root);
   return leftPath;
  }
  if (rightPath != null)
  {
   rightPath.add(0, root);
   return rightPath;
  }
  return null;
 }

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

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