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

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.

S. No.	Input Node	Ancestors
1	B	A (60 )
2	D or E	A B (60, 50)
3	C	A (60)
4	F or G	A C (60, 90)

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.

parent nodes recursive algorithm — Fig 2: Ancestor of Node E in a 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.

ancestors given node binary tree — Fig 3: Ancestor of Node G in a binary tree

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

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

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

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

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

1.) PrintAncestorOfNode Class:

2.) Node Class:

3.) App Class:

Output – ancestor of given node using recursive algorithm in java

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

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

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

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

1.) PrintAncestorOfNode Class:

2.) Node Class:

3.) App Class:

Output – ancestor of given node using recursive algorithm in java

You may also like: