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