Print ancestors of node in a binary tree (java/ recursive/ examples)

• Given a binary tree, print ancestors of given node using depth first search recursive algorithm
  • We will traverse the binary tree using recursive preOrder traversal.
  • Print all nodes which we have visited, to reach a given node.
  • We will discuss the algorithm with couple of examples.
• The algorithm is quite similar to finding a least or lowest common ancestor in a binary tree.

Given input node and its corresponding ancestor nodes are shown in a table.

Example 1:  Print ancestor of node E (80) in a binary tree using java

We will use pre order traversal to traverse the binary tree.

• Visit Root Node A (60) (Refer Fig 2)
• Compare the data of node A with input node (80)
  • 60 == 80 ?, its not equal, traverse left & right subtree.
• Visit left subtree of Node A
  • Compare the data of root B (50) with 80
    • It does not match, traverse its child nodes
  • Visit Left child of Node B (i.e.Node D)
    • Compare the data of node D (25) with 80
      • It does not match, traverse its child nodes
      • return false
  • Visit right child of B (i.e.Node E)
    • Compare the data of root E (80) with 80
      • Found the node & return true.
• Once we got true from subtree, we will print all ancestors of given node.

Example 2:  Print ancestor of Node G (45) in a binary tree using java

We will analyze the binary tree shown in Fig 3. We will search the node in a binary tree and will print all nodes which we have visited during traversal. The algorithm is quite similar to example 1 algorithm.

Time complexity of algorithm is O(n).

Program – print ancestor of given node in binary tree (java/ recursive)

1.) PrintAncestorOfNode Class:

• PrintAncestorOfNode class is responsible for printing ancestors of a given node.
• Traverse the binary tree using depth first search recursive algorithm.

  
package org.learn.Question;

public class PrintAncestorOfNode {
 public static boolean printAncestorOfNode(Node root, int data) {
  if(null == root) {
   return false;
  }
  //we found the node
  if(root.data == data) {
   return true;
  }
  boolean bFoundOnLeft = printAncestorOfNode(root.left,data);
  if(bFoundOnLeft) {
   System.out.printf("%d ",root.data);
   return bFoundOnLeft;
  }
  boolean bFoundOnRight = printAncestorOfNode(root.right,data);
  if(bFoundOnRight) {
   System.out.printf("%d ",root.data);
   return bFoundOnRight;
  }
  return false;
 } 
}

2.) Node Class:

• Node class is representing the nodes of a binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class: 

• We are creating the binary tree in main method.
• We are calling method of PrintAncestorOfNode class, to print ancestors of a given input node.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.PrintAncestorOfNode;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(60);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(90);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(75);
  Node G = Node.createNode(45);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;

  int iNode = 50;
  System.out.printf("Ancestor of Node %d is : \n", iNode);
  PrintAncestorOfNode.printAncestorOfNode(A, iNode);

  iNode = 45;
  System.out.printf("\nAncestor of Node %d is : \n", iNode);
  PrintAncestorOfNode.printAncestorOfNode(A, iNode);

  iNode = 25;
  System.out.printf("\nAncestor of Node %d is : \n", iNode);
  PrintAncestorOfNode.printAncestorOfNode(A, iNode);
 }
}

Output – ancestor of given node using recursive algorithm in java

Ancestor of Node 50 is : 
60 
Ancestor of Node 45 is : 
90 60 
Ancestor of Node 25 is : 
50 60 

Download code – print ancestor(s) of node binary tree recursive java