Type like pro


Find path of a node from root

Find path of a node from root


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


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.


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)

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