Print Path From Root to the Given Node of a Binary Tree

In this article, we will implement the algorithm to print the path from the root node to any given node. We will be using a stack to keep a track of the path and implement the algorithm in Java.

The path from the root node 5 to the node 25 would be 5 10 15 25

The main idea here is first we traverse the tree till we find the node that we are searching for. Either the node will be found in the right or left subtree and based on this we will push each node in the path to the corresponding stack.

Binary Tree Node Implementation

Below is our node class implementation. Each node has its left and right node and the data.

public class BinaryTreeNode {

    private int data;
    private BinaryTreeNode leftNode;
    private BinaryTreeNode rightNode;

//setters and getters

Print Path from Root Node to the Given Node

Initially, the stack will be null untill we find the node. The node would be found either in the left or the right subtree. If the node is found in the left subtree then the right stack will be always null and hence all the left nodes in the path from the node 25 to the root will be pushed to the leftStack. After O((n) time complexity we have our all nodes in the stack those are present from the root to the node that we are looking for.

public static void printPathBetween(BinaryTreeNode root, BinaryTreeNode n1){
       Stack<BinaryTreeNode> stack1 = printPath(root, n1);
       while (!stack1.isEmpty()){
           System.out.println(stack1.pop().getData());
       }
    }

    private static Stack<BinaryTreeNode> printPath(BinaryTreeNode root, BinaryTreeNode n1) {
        if (root == null){
            return null;
        }
        if (root == n1){
            Stack<BinaryTreeNode> stack = new Stack<>();
            stack.push(n1);
            return stack;
        }
        Stack leftStack = printPath(root.getLeftNode(), n1);
        Stack rightStack =  printPath(root.getRightNode(), n1);
        if (leftStack != null){
            leftStack.push(root);
            return leftStack;
        }
        if (rightStack != null){
            rightStack.push(root);
            return rightStack;
        }
        return null;
    }

The same algorithm can be used to find the path between any two nodes assuming the first node be the root. Suppoose we want to find the path between the node 14 and 25. First find the node 14 in the tree using BFS and once this is found assuming the node 14 to be the root, we can print the path between 14 and 25.

Tree Runner

Below is our main method. We are passing the node 25 to print the path from the root node.

public static void main(String[] args){
        BinaryTreeNode root = new BinaryTreeNode(5);
        root.setLeftNode(new BinaryTreeNode(7));
        root.setRightNode(new BinaryTreeNode(10));
        root.getLeftNode().setLeftNode(new BinaryTreeNode(14));
        root.getLeftNode().setRightNode(new BinaryTreeNode(19));

        root.getRightNode().setLeftNode(new BinaryTreeNode(30));
        root.getRightNode().setRightNode(new BinaryTreeNode(15));

        root.getRightNode().getRightNode().setLeftNode(new BinaryTreeNode(25));

        PathBetweenNodes.printPathBetween(root, root.getRightNode().getRightNode().getLeftNode());

    }

Conclusion

In this article, we implemented the algorithm to print the path from the root node to any given node in Java using stack.