Given a Binary Tree, the task is to print all root-to-leaf paths of this tree whose xor value is non-zero.
Examples:
Input:
10
/ \
10 3
/ \
10 3
/ \ / \
7 3 42 13
/
7
Output:
10 3 10 7
10 3 3 42
Explanation:
All the paths in the given binary tree are :
{10, 10} xor value of the path is
= 10 ^ 10 = 0
{10, 3, 10, 7} xor value of the path is
= 10 ^ 3 ^ 10 ^ 7 != 0
{10, 3, 3, 42} xor value of the path is
= 10 ^ 3 ^ 3 ^ 42 != 0
{10, 3, 10, 3} xor value of the path is
= 10 ^ 3 ^ 10 ^ 3 = 0
{10, 3, 3, 13, 7} xor value of the path is
= 10 ^ 3 ^ 3 ^ 13 ^ 7 = 0.
Hence, {10, 3, 10, 7} and {10, 3, 3, 42} are
the paths whose xor value is non-zero.
Input:
5
/ \
21 77
/ \ \
5 21 16
\ /
5 3
Output :
5 21 5
5 77 16 3
Explanation:
{5, 21, 5} and {5, 77, 16, 3} are the paths
whose xor value is non-zero.
Approach:
To solve the problem mentioned above the main idea is to traverse the tree and check if the xor of all the elements in that path is zero or not.
- We need to traverse the tree recursively using Pre-Order Traversal.
- For each node keep calculating the XOR of the path from root till the current node.
- If the node is a leaf node that is left and the right child for the current nodes are NULL then we check if the xor value of the path is non-zero or not, if it is then we print the entire path.
Below is the implementation of the above approach:
C++
// C++ program to Print all the Paths of a// Binary Tree whose XOR gives a non-zero value#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int key; struct Node *left, *right;};// Function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to check whether Path// is has non-zero xor value or notbool PathXor(vector<int>& path){ int ans = 0; // Iterating through the array // to find the xor value for (auto x : path) { ans ^= x; } return (ans != 0);}// Function to print a pathvoid printPaths(vector<int>& path){ for (auto x : path) { cout << x << " "; } cout << endl;}// Function to find the paths of// binary tree having non-zero xor valuevoid findPaths(struct Node* root, vector<int>& path){ // Base case if (root == NULL) return; // Store the value in path vector path.push_back(root->key); // Recursively call for left sub tree findPaths(root->left, path); // Recursively call for right sub tree findPaths(root->right, path); // Condition to check, if leaf node if (root->left == NULL && root->right == NULL) { // Condition to check, // if path has non-zero xor or not if (PathXor(path)) { // Print the path printPaths(path); } } // Remove the last element // from the path vector path.pop_back();}// Function to find the paths// having non-zero xor valuevoid printPaths(struct Node* node){ vector<int> path; findPaths(node, path);}// Driver Codeint main(){ /* 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(10); root->right = newNode(3); root->right->left = newNode(10); root->right->right = newNode(3); root->right->left->left = newNode(7); root->right->left->right = newNode(3); root->right->right->left = newNode(42); root->right->right->right = newNode(13); root->right->right->right->left = newNode(7); // Print non-zero XOR Paths printPaths(root); return 0;} |
Java
// Java program to Print all the Paths of a// Binary Tree whose XOR gives a non-zero valueimport java.util.*;class GFG{// A Tree nodestatic class Node { int key; Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to check whether Path// is has non-zero xor value or notstatic boolean PathXor(Vector<Integer> path){ int ans = 0; // Iterating through the array // to find the xor value for (int x : path) { ans ^= x; } return (ans != 0);}// Function to print a pathstatic void printPaths(Vector<Integer> path){ for (int x : path) { System.out.print(x + " "); } System.out.println();}// Function to find the paths of// binary tree having non-zero xor valuestatic void findPaths(Node root, Vector<Integer> path){ // Base case if (root == null) return; // Store the value in path vector path.add(root.key); // Recursively call for left sub tree findPaths(root.left, path); // Recursively call for right sub tree findPaths(root.right, path); // Condition to check, if leaf node if (root.left == null && root.right == null) { // Condition to check, // if path has non-zero xor or not if (PathXor(path)) { // Print the path printPaths(path); } } // Remove the last element // from the path vector path.remove(path.size() - 1);}// Function to find the paths// having non-zero xor valuestatic void printPaths(Node node){ Vector<Integer> path = new Vector<Integer>(); findPaths(node, path);}// Driver Codepublic static void main(String[] args){ /* 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(10); root.right = newNode(3); root.right.left = newNode(10); root.right.right = newNode(3); root.right.left.left = newNode(7); root.right.left.right = newNode(3); root.right.right.left = newNode(42); root.right.right.right = newNode(13); root.right.right.right.left = newNode(7); // Print non-zero XOR Paths printPaths(root);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program to print all # the paths of a Binary Tree # whose XOR gives a non-zero value# A Tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None# Function to check whether Path# is has non-zero xor value or notdef PathXor(path: list) -> bool: ans = 0 # Iterating through the array # to find the xor value for x in path: ans ^= x return (ans != 0)# Function to print a pathdef printPathsList(path: list) -> None: for x in path: print(x, end = " ") print()# Function to find the paths of# binary tree having non-zero xor valuedef findPaths(root: Node, path: list) -> None: # Base case if (root == None): return # Store the value in path vector path.append(root.key) # Recursively call for left sub tree findPaths(root.left, path) # Recursively call for right sub tree findPaths(root.right, path) # Condition to check, if leaf node if (root.left == None and root.right == None): # Condition to check, if path # has non-zero xor or not if (PathXor(path)): # Print the path printPathsList(path) # Remove the last element # from the path vector path.pop()# Function to find the paths# having non-zero xor valuedef printPaths(node: Node) -> None: path = [] newNode = node findPaths(newNode, path)# Driver Codeif __name__ == "__main__": ''' 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 ''' # Create Binary Tree as shown root = Node(10) root.left = Node(10) root.right = Node(3) root.right.left = Node(10) root.right.right = Node(3) root.right.left.left = Node(7) root.right.left.right = Node(3) root.right.right.left = Node(42) root.right.right.right = Node(13) root.right.right.right.left = Node(7) # Print non-zero XOR Paths printPaths(root)# This code is contributed by sanjeev2552 |
C#
// C# program to Print all the Paths of a// Binary Tree whose XOR gives a non-zero valueusing System;using System.Collections.Generic;class GFG{// A Tree nodeclass Node { public int key; public Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to check whether Path// is has non-zero xor value or notstatic bool PathXor(List<int> path){ int ans = 0; // Iterating through the array // to find the xor value foreach (int x in path) { ans ^= x; } return (ans != 0);}// Function to print a pathstatic void printPaths(List<int> path){ foreach (int x in path) { Console.Write(x + " "); } Console.WriteLine();}// Function to find the paths of// binary tree having non-zero xor valuestatic void findPaths(Node root, List<int> path){ // Base case if (root == null) return; // Store the value in path vector path.Add(root.key); // Recursively call for left sub tree findPaths(root.left, path); // Recursively call for right sub tree findPaths(root.right, path); // Condition to check, if leaf node if (root.left == null && root.right == null) { // Condition to check, // if path has non-zero xor or not if (PathXor(path)) { // Print the path printPaths(path); } } // Remove the last element // from the path vector path.RemoveAt(path.Count - 1);}// Function to find the paths// having non-zero xor valuestatic void printPaths(Node node){ List<int> path = new List<int>(); findPaths(node, path);}// Driver Codepublic static void Main(String[] args){ /* 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(10); root.right = newNode(3); root.right.left = newNode(10); root.right.right = newNode(3); root.right.left.left = newNode(7); root.right.left.right = newNode(3); root.right.right.left = newNode(42); root.right.right.right = newNode(13); root.right.right.right.left = newNode(7); // Print non-zero XOR Paths printPaths(root);}}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to Print all the Paths of a // Binary Tree whose XOR gives a non-zero value // A Tree node class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } // Function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Function to check whether Path // is has non-zero xor value or not function PathXor(path) { let ans = 0; // Iterating through the array // to find the xor value for (let x = 0; x < path.length; x++) { ans ^= path[x]; } if(ans != 0) { return true; } else{ return false; } } // Function to print a path function printPaths(path) { for (let x = 0; x < path.length; x++) { document.write(path[x] + " "); } document.write("</br>"); } // Function to find the paths of // binary tree having non-zero xor value function findPaths(root, path) { // Base case if (root == null) return; // Store the value in path vector path.push(root.key); // Recursively call for left sub tree findPaths(root.left, path); // Recursively call for right sub tree findPaths(root.right, path); // Condition to check, if leaf node if (root.left == null && root.right == null) { // Condition to check, // if path has non-zero xor or not if (PathXor(path)) { // Print the path printPaths(path); } } // Remove the last element // from the path vector path.pop(); } // Function to find the paths // having non-zero xor value function printpaths(node) { let path = []; findPaths(node, path); } /* 10 / \ 10 3 / \ 10 3 / \ / \ 7 3 42 13 / 7 */ // Create Binary Tree as shown let root = newNode(10); root.left = newNode(10); root.right = newNode(3); root.right.left = newNode(10); root.right.right = newNode(3); root.right.left.left = newNode(7); root.right.left.right = newNode(3); root.right.right.left = newNode(42); root.right.right.right = newNode(13); root.right.right.right.left = newNode(7); // Print non-zero XOR Paths printpaths(root); </script> |
Output:
10 3 10 7 10 3 3 42
Time complexity: O(N) where N is no of nodes in given binary tree
Space Complexity: O(h) where h is the height of the binary tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
