Given a binary tree with distinct nodes(no two nodes have the same have data values). The problem is to print the path from root to a given node x. If node x is not present then print “No Path”.
Examples:
Input : 1
/
2 3
/ /
4 5 6 7
x = 5
Output : 1->2->5
Approach: Create a recursive function that traverses the different path in the binary tree to find the required node x. If node x is present then it returns true and accumulates the path nodes in some array arr[]. Else it returns false.
Following are the cases during the traversal:
- If root = NULL, return false.
- push the root’s data into arr[].
- if root’s data = x, return true.
- if node x is present in root’s left or right subtree, return true.
- Else remove root’s data value from arr[] and return false.
This recursive function can be accessed from other function to check whether node x is present or not and if it is present, then the path nodes can be accessed from arr[]. You can define arr[] globally or pass its reference to the recursive function.
C++
// C++ implementation to print the path from root // to a given node in a binary tree #include <bits/stdc++.h> using namespace std; // structure of a node of binary tree struct Node { int data; Node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct Node* getNode(int data) { struct Node *newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path bool hasPath(Node *root, vector<int>& arr, int x) { // if root is NULL // there is no path if (!root) return false; // push the node's value in 'arr' arr.push_back(root->data); // if it is the required node // return true if (root->data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root->left, arr, x) || hasPath(root->right, arr, x)) return true; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.pop_back(); return false; } // function to print the path from root to the // given node if the node lies in the binary tree void printPath(Node *root, int x) { // vector to store the path vector<int> arr; // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for (int i=0; i<arr.size()-1; i++) cout << arr[i] << "->"; cout << arr[arr.size() - 1]; } // 'x' is not present in the binary tree else cout << "No Path"; } // Driver program to test above int main() { // binary tree formation struct Node *root = getNode(1); root->left = getNode(2); root->right = getNode(3); root->left->left = getNode(4); root->left->right = getNode(5); root->right->left = getNode(6); root->right->right = getNode(7); int x = 5; printPath(root, x); return 0; } |
Java
// Java implementation to print the path from root // to a given node in a binary tree import java.util.ArrayList; public class PrintPath { // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path public static boolean hasPath(Node root, ArrayList<Integer> arr, int x) { // if root is NULL // there is no path if (root==null) return false; // push the node's value in 'arr' arr.add(root.data); // if it is the required node // return true if (root.data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root.left, arr, x) || hasPath(root.right, arr, x)) return true; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.remove(arr.size()-1); return false; } // function to print the path from root to the // given node if the node lies in the binary tree public static void printPath(Node root, int x) { // ArrayList to store the path ArrayList<Integer> arr=new ArrayList<>(); // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for (int i=0; i<arr.size()-1; i++) System.out.print(arr.get(i)+"->"); System.out.print(arr.get(arr.size() - 1)); } // 'x' is not present in the binary tree else System.out.print("No Path"); } public static void main(String args[]) { Node root=new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); int x=5; printPath(root, x); } } // A node of binary tree class Node { int data; Node left, right; Node(int data) { this.data=data; left=right=null; } }; //This code is contributed by Gaurav Tiwari |
Python3
# Python3 implementation to prthe path from # root to a given node in a binary tree # Helper Class that allocates a new node # with the given data and None left and # right pointers. class getNode: def __init__(self, data): self.data = data self.left = self.right = None # Returns true if there is a path from # root to the given node. It also # populates 'arr' with the given path def hasPath(root, arr, x): # if root is None there is no path if (not root): return False # push the node's value in 'arr' arr.append(root.data) # if it is the required node # return true if (root.data == x): return True # else check whether the required node # lies in the left subtree or right # subtree of the current node if (hasPath(root.left, arr, x) or hasPath(root.right, arr, x)): return True # required node does not lie either in # the left or right subtree of the current # node. Thus, remove current node's value # from 'arr'and then return false arr.pop(-1) return False # function to prthe path from root to # the given node if the node lies in # the binary tree def printPath(root, x): # vector to store the path arr = [] # if required node 'x' is present # then prthe path if (hasPath(root, arr, x)): for i in range(len(arr) - 1): print(arr[i], end = "->") print(arr[len(arr) - 1]) # 'x' is not present in the # binary tree else: print("No Path") # Driver Code if __name__ == '__main__': # binary tree formation root = getNode(1) root.left = getNode(2) root.right = getNode(3) root.left.left = getNode(4) root.left.right = getNode(5) root.right.left = getNode(6) root.right.right = getNode(7) x = 5 printPath(root, x) # This code is contributed by PranchalK |
C#
// C# implementation to print the path from root // to a given node in a binary tree using System; using System.Collections; using System.Collections.Generic; class PrintPath { // A node of binary tree public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path public static Boolean hasPath(Node root, List<int> arr, int x) { // if root is NULL // there is no path if (root == null) return false; // push the node's value in 'arr' arr.Add(root.data); // if it is the required node // return true if (root.data == x) return true; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root.left, arr, x) || hasPath(root.right, arr, x)) return true; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.RemoveAt(arr.Count - 1); return false; } // function to print the path from root to the // given node if the node lies in the binary tree public static void printPath(Node root, int x) { // List to store the path List<int> arr = new List<int>(); // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for (int i = 0; i < arr.Count - 1; i++) Console.Write(arr[i]+"->"); Console.Write(arr[arr.Count - 1]); } // 'x' is not present in the binary tree else Console.Write("No Path"); } // Driver code public static void Main(String []args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); int x=5; printPath(root, x); } } // This code is contributed by Arnab Kundu |
Output:
1->2->5
Time complexity: O(n) in worst case, where n is the number of nodes in the binary tree.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments