Posted on by Kalkicode
Code Recursion

# Print all the paths in the binary tree whose xor is non-zero

The problem involves finding and printing all the paths in a binary tree where the XOR of the values in the path is non-zero. The XOR of a path is calculated by performing bitwise XOR operation on the values of nodes in the path.

## Problem Statement

Given a binary tree, the task is to find and print all the paths from the root to the leaves of the tree such that the XOR of the values of nodes in the path is non-zero.

## Example Scenario

Consider the binary tree shown below:

``````
4
/   \
9     7
/ \     \
2   4     4
/ \   / \
6   9 5   7
/         \
9           15``````

The paths with non-zero XOR are: [4, 9, 2], [4, 9, 4, 6, 9], [4, 7, 4, 5, 15].

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach to traverse the binary tree while maintaining a current path and a running XOR value. At each step, we update the current XOR value based on the current node's value and recursively traverse its left and right subtrees.

## Pseudocode

``````void findNonZeroXorPath(TreeNode node, ArrayList path, int xorValue)
{
if (node == null)
return;

xorValue ^= node.data;

if (node.left == null && node.right == null && xorValue != 0)
printPath(path);

findNonZeroXorPath(node.left, path, xorValue);
findNonZeroXorPath(node.right, path, xorValue);

path.remove(path.size() - 1);
}``````

## Algorithm Explanation

1. Implement a function `findNonZeroXorPath` that takes three arguments: `node` (current node), `path` (list of nodes in the path), and `xorValue` (current XOR value of the path).
2. Base case: If the current node is null, return.
3. Add the current node's value to the path and update the XOR value by performing the XOR operation.
4. If the current node is a leaf node and the XOR value is non-zero, print the path.
5. Recursively traverse the left and right subtrees while updating the path and XOR value.
6. After processing the current node, remove it from the path to backtrack.

## Program Solution

``````import java.util.ArrayList;
/*
Java Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.count = 0;
}
// Display given path
public void printPath(ArrayList < Integer > path)
{
int i = 0;
// print path
while (i < path.size())
{
// print path node
System.out.print(" " + path.get(i));
i++;
}
System.out.print("\n");
}
// Find all root to given node path using recursion
public void findNonZeoXorPath(TreeNode point,
ArrayList < Integer > path, int xOr)
{
if (point == null)
{
return;
}
if (point.left == null && point.right == null && (xOr ^ point.data) != 0)
{
this.count++;
printPath(path);
}
// Visit left and right subtree using recursion
findNonZeoXorPath(point.left, path, xOr ^ point.data);
findNonZeoXorPath(point.right, path,  xOr ^ point.data);
// Remove last node in path
path.remove(path.size() - 1);
}
// Handles the request of finding non zero xor path in tree
public void nonZeoXorPath()
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
ArrayList < Integer > path = new ArrayList < Integer > ();
this.count = 0;
// print non zero xor path
findNonZeoXorPath(this.root, path, 0);

if (this.count == 0)
{
// When have no resultant path
System.out.print("None");
}
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);

// Check
tree.nonZeoXorPath();

}
}``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````// Include header file
#include <iostream>
#include <vector>
using namespace std;

/*
C++ Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
int count;
BinaryTree()
{
this->root = NULL;
this->count = 0;
}
// Display given path
void printPath(vector < int > path)
{
int i = 0;
// print path
while (i < path.size())
{
// print path node
cout << " " << path.at(i);
i++;
}
cout << "\n";
}
// Find all root to given node path using recursion
void findNonZeoXorPath(TreeNode *point, vector < int > path, int xOr)
{
if (point == NULL)
{
return;
}
path.push_back(point->data);
if (point->left == NULL
&& point->right == NULL
&& (xOr ^ point->data) != 0)
{
this->count++;
this->printPath(path);
}
// Visit left and right subtree using recursion
this->findNonZeoXorPath(point->left, path, xOr ^ point->data);
this->findNonZeoXorPath(point->right, path, xOr ^ point->data);
// Remove last node in path
path.pop_back();
}
// Handles the request of finding non zero xor path in tree
void nonZeoXorPath()
{
if (this->root == NULL)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
vector < int > path ;
this->count = 0;
// print non zero xor path
this->findNonZeoXorPath(this->root, path, 0);
if (this->count == 0)
{
// When have no resultant path
cout << "None";
}
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(9);
tree->root->left->right = new TreeNode(4);
tree->root->left->right->left = new TreeNode(6);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(9);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(4);
tree->root->right->right->right = new TreeNode(7);
tree->root->right->right->left = new TreeNode(5);
tree->root->right->right->left->right = new TreeNode(15);
// Check
tree->nonZeoXorPath();
return 0;
}``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.count = 0;
}
// Display given path
public void printPath(List < int > path)
{
int i = 0;
// print path
while (i < path.Count)
{
// print path node
Console.Write(" " + path[i]);
i++;
}
Console.Write("\n");
}
// Find all root to given node path using recursion
public void findNonZeoXorPath(TreeNode point, List < int > path, int xOr)
{
if (point == null)
{
return;
}
if (point.left == null && point.right == null
&& (xOr ^ point.data) != 0)
{
this.count++;
this.printPath(path);
}
// Visit left and right subtree using recursion
this.findNonZeoXorPath(point.left, path, xOr ^ point.data);
this.findNonZeoXorPath(point.right, path, xOr ^ point.data);
// Remove last node in path
path.RemoveAt(path.Count - 1);
}
// Handles the request of finding non zero xor path in tree
public void nonZeoXorPath()
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
List < int > path = new List < int > ();
this.count = 0;
// print non zero xor path
this.findNonZeoXorPath(this.root, path, 0);
if (this.count == 0)
{
// When have no resultant path
Console.Write("None");
}
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
// Check
tree.nonZeoXorPath();
}
}``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````<?php
/*
Php Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public \$count;
public	function __construct()
{
\$this->root = NULL;
\$this->count = 0;
}
// Display given path
public	function printPath(\$path)
{
\$i = 0;
// print path
while (\$i < count(\$path))
{
// print path node
echo(" ".\$path[\$i]);
\$i++;
}
echo("\n");
}
// Find all root to given node path using recursion
public	function findNonZeoXorPath(\$point, \$path, \$xOr)
{
if (\$point == NULL)
{
return;
}
\$path[] = \$point->data;
if (\$point->left == NULL
&& \$point->right == NULL
&& (\$xOr ^ \$point->data) != 0)
{
\$this->count++;
\$this->printPath(\$path);
}
// Visit left and right subtree using recursion
\$this->findNonZeoXorPath(\$point->left,
\$path, \$xOr ^ \$point->data);
\$this->findNonZeoXorPath(\$point->right,
\$path, \$xOr ^ \$point->data);
// Remove last node in path
array_pop(\$path);
}
// Handles the request of finding non zero xor path in tree
public	function nonZeoXorPath()
{
if (\$this->root == NULL)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
\$path = array();
\$this->count = 0;
// print non zero xor path
\$this->findNonZeoXorPath(\$this->root, \$path, 0);
if (\$this->count == 0)
{
// When have no resultant path
echo("None");
}
}
}
}

function main()
{
// Create new binary tree
\$tree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
\$tree->root = new TreeNode(4);
\$tree->root->left = new TreeNode(9);
\$tree->root->left->right = new TreeNode(4);
\$tree->root->left->right->left = new TreeNode(6);
\$tree->root->left->right->left->left = new TreeNode(9);
\$tree->root->left->right->right = new TreeNode(9);
\$tree->root->left->left = new TreeNode(2);
\$tree->root->right = new TreeNode(7);
\$tree->root->right->right = new TreeNode(4);
\$tree->root->right->right->right = new TreeNode(7);
\$tree->root->right->right->left = new TreeNode(5);
\$tree->root->right->right->left->right = new TreeNode(15);
// Check
\$tree->nonZeoXorPath();
}
main();``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````/*
Node JS Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
this.count = 0;
}
// Display given path
printPath(path)
{
var i = 0;
// print path
while (i < path.length)
{
// print path node
process.stdout.write(" " + path[i]);
i++;
}
process.stdout.write("\n");
}
// Find all root to given node path using recursion
findNonZeoXorPath(point, path, xOr)
{
if (point == null)
{
return;
}
path.push(point.data);
if (point.left == null
&& point.right == null
&& (xOr ^ point.data) != 0)
{
this.count++;
this.printPath(path);
}
// Visit left and right subtree using recursion
this.findNonZeoXorPath(point.left, path, xOr ^ point.data);
this.findNonZeoXorPath(point.right, path, xOr ^ point.data);
// Remove last node in path
path.pop();
}
// Handles the request of finding non zero xor path in tree
nonZeoXorPath()
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
var path = [];
this.count = 0;
// print non zero xor path
this.findNonZeoXorPath(this.root, path, 0);
if (this.count == 0)
{
// When have no resultant path
process.stdout.write("None");
}
}
}
}

function main()
{
// Create new binary tree
var tree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
// Check
tree.nonZeoXorPath();
}
main();``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````#    Python 3 Program
#    Print all the paths in the binary tree whose xor is non-zero

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :
def __init__(self) :
self.root = None
self.count = 0

#  Display given path
def printPath(self, path) :
i = 0
#  print path
while (i < len(path)) :
#  print path node
print(" ", path[i], end = "")
i += 1

print(end = "\n")

#  Find all root to given node path using recursion
def findNonZeoXorPath(self, point, path, xOr) :
if (point == None) :
return

path.append(point.data)
if (point.left == None and point.right == None
and (xOr ^ point.data) != 0) :
self.count += 1
self.printPath(path)

#  Visit left and right subtree using recursion
self.findNonZeoXorPath(point.left, path, xOr ^ point.data)
self.findNonZeoXorPath(point.right, path, xOr ^ point.data)
#  Remove last node in path
del path[len(path) - 1]

#  Handles the request of finding non zero xor path in tree
def nonZeoXorPath(self) :
if (self.root == None) :
#  Empty Tree
return
else :
#  This is use to collect path
path = []
self.count = 0
#  print non zero xor path
self.findNonZeoXorPath(self.root, path, 0)
if (self.count == 0) :
#  When have no resultant path
print("None", end = "")

def main() :
#  Create new binary tree
tree = BinaryTree()
#     4
#    /   \
#   9     7
#  / \      \
# 2   4      4
#    / \    / \
#   6   9  5   7
#  /        \
# 9          15
# -----------------
# Constructing binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(9)
tree.root.left.right = TreeNode(4)
tree.root.left.right.left = TreeNode(6)
tree.root.left.right.left.left = TreeNode(9)
tree.root.left.right.right = TreeNode(9)
tree.root.left.left = TreeNode(2)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(4)
tree.root.right.right.right = TreeNode(7)
tree.root.right.right.left = TreeNode(5)
tree.root.right.right.left.right = TreeNode(15)
#  Check
tree.nonZeoXorPath()

if __name__ == "__main__": main()``````

#### input

``````  4  9  2
4  9  4  6  9
4  7  4  5  15``````
``````#    Ruby Program
#    Print all the paths in the binary tree whose xor is non-zero

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root, :count
def initialize()
self.root = nil
self.count = 0
end

#  Display given path
def printPath(path)
i = 0
#  print path
while (i < path.length)
#  print path node
print(" ", path[i])
i += 1
end

print("\n")
end

#  Find all root to given node path using recursion
def findNonZeoXorPath(point, path, xOr)
if (point == nil)
return
end

path.push(point.data)
if (point.left == nil &&
point.right == nil &&
(xOr ^ point.data) != 0)
self.count += 1
self.printPath(path)
end

#  Visit left and right subtree using recursion
self.findNonZeoXorPath(point.left, path, xOr ^ point.data)
self.findNonZeoXorPath(point.right, path, xOr ^ point.data)
#  Remove last node in path
path.delete_at(path.length - 1)
end

#  Handles the request of finding non zero xor path in tree
def nonZeoXorPath()
if (self.root == nil)
#  Empty Tree
return
else

#  This is use to collect path
path = []
self.count = 0
#  print non zero xor path
self.findNonZeoXorPath(self.root, path, 0)
if (self.count == 0)
#  When have no resultant path
print("None")
end

end

end

end

def main()
#  Create new binary tree
tree = BinaryTree.new()
#     4
#    /   \
#   9     7
#  / \      \
# 2   4      4
#    / \    / \
#   6   9  5   7
#  /        \
# 9          15
# -----------------
# Constructing binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(9)
tree.root.left.right = TreeNode.new(4)
tree.root.left.right.left = TreeNode.new(6)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.left.right.right = TreeNode.new(9)
tree.root.left.left = TreeNode.new(2)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(7)
tree.root.right.right.left = TreeNode.new(5)
tree.root.right.right.left.right = TreeNode.new(15)
#  Check
tree.nonZeoXorPath()
end

main()``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15
``````
``````import scala.collection.mutable._;
/*
Scala Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class BinaryTree(var root: TreeNode,
var count: Int)
{
def this()
{
this(null,0);
}
// Display given path
def printPath(path: ArrayBuffer[Int]): Unit = {
var i: Int = 0;
// print path
while (i < path.size)
{
// print path node
print(" " + path(i));
i += 1;
}
print("\n");
}
// Find all root to given node path using recursion
def findNonZeoXorPath(point: TreeNode,
path: ArrayBuffer[Int], xOr: Int): Unit = {
if (point == null)
{
return;
}
path += point.data;
if (point.left == null && point.right == null
&& (xOr ^ point.data) != 0)
{
this.count += 1;
printPath(path);
}
// Visit left and right subtree using recursion
findNonZeoXorPath(point.left, path, xOr ^ point.data);
findNonZeoXorPath(point.right, path, xOr ^ point.data);
// Remove last node in path
path.remove(path.size - 1);
}
// Handles the request of finding non zero xor path in tree
def nonZeoXorPath(): Unit = {
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
this.count = 0;
// print non zero xor path
findNonZeoXorPath(this.root, path, 0);
if (this.count == 0)
{
// When have no resultant path
print("None");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree: BinaryTree = new BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(9);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(15);
// Check
tree.nonZeoXorPath();
}
}``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````
``````import Foundation;
/*
Swift 4 Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
var count: Int;
init()
{
self.root = nil;
self.count = 0;
}
// Display given path
func printPath(_ path: [Int])
{
var i = 0;
// print path
while (i < path.count)
{
// print path node
print(" ", path[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Find all root to given node path using recursion
func findNonZeoXorPath(_ point: TreeNode? ,
_ path : inout[Int], _ xOr: Int)
{
if (point == nil)
{
return;
}
path.append(point!.data);
if (point!.left == nil && point!.right == nil
&& (xOr ^ point!.data)  != 0)
{
self.count += 1;
self.printPath(path);
}
// Visit left and right subtree using recursion
self.findNonZeoXorPath(point!.left, &path, xOr ^ point!.data);
self.findNonZeoXorPath(point!.right, &path, xOr ^ point!.data);
// Remove last node in path
path.removeLast();
}
// Handles the request of finding non zero xor path in tree
func nonZeoXorPath()
{
if (self.root == nil)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
var path = [Int]();
self.count = 0;
// print non zero xor path
self.findNonZeoXorPath(self.root, &path, 0);
if (self.count == 0)
{
// When have no resultant path
print("None", terminator: "");
}
}
}
}
func main()
{
// Create new binary tree
let tree = BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(9);
tree.root!.left!.right = TreeNode(4);
tree.root!.left!.right!.left = TreeNode(6);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.left!.right!.right = TreeNode(9);
tree.root!.left!.left = TreeNode(2);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(7);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.right!.right!.left!.right = TreeNode(15);
// Check
tree.nonZeoXorPath();
}
main();``````

#### input

``````  4  9  2
4  9  4  6  9
4  7  4  5  15``````
``````/*
Kotlin Program
Print all the paths in the binary tree whose xor is non-zero
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
var count: Int;
constructor()
{
this.root = null;
this.count = 0;
}
// Display given path
fun printPath(path: MutableList < Int > ): Unit
{
var i: Int = 0;
// print path
while (i < path.size)
{
// print path node
print(" " + path[i]);
i += 1;
}
print("\n");
}
// Find all root to given node path using recursion
fun findNonZeoXorPath(point: TreeNode ? ,
path : MutableList < Int >  , xOr : Int): Unit
{
if (point == null)
{
return;
}
if (point.left == null
&& point.right == null
&& (xOr xor point.data) != 0)
{
this.count += 1;
this.printPath(path);
}
// Visit left and right subtree using recursion
this.findNonZeoXorPath(point.left, path, xOr xor point.data);
this.findNonZeoXorPath(point.right, path, xOr xor point.data);
// Remove last node in path
path.removeAt(path.size - 1);
}
// Handles the request of finding non zero xor path in tree
fun nonZeoXorPath(): Unit
{
if (this.root == null)
{
// Empty Tree
return;
}
else
{
// This is use to collect path
val path: MutableList < Int > = mutableListOf < Int > ();
this.count = 0;
// print non zero xor path
this.findNonZeoXorPath(this.root, path, 0);
if (this.count == 0)
{
// When have no resultant path
print("None");
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree: BinaryTree = BinaryTree();
/*
4
/   \
9     7
/ \      \
2   4      4
/ \    / \
6   9  5   7
/        \
9          15
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(9);
tree.root?.left?.right = TreeNode(4);
tree.root?.left?.right?.left = TreeNode(6);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.left?.right?.right = TreeNode(9);
tree.root?.left?.left = TreeNode(2);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(4);
tree.root?.right?.right?.right = TreeNode(7);
tree.root?.right?.right?.left = TreeNode(5);
tree.root?.right?.right?.left?.right = TreeNode(15);
// Check
tree.nonZeoXorPath();
}``````

#### input

`````` 4 9 2
4 9 4 6 9
4 7 4 5 15``````

## Output Explanation

The code implements the algorithm and finds and prints all the paths in the binary tree where the XOR of the values in the path is non-zero. It demonstrates the result by printing each path.

## Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal. The space complexity is O(H), where H is the height of the binary tree, due to the recursive call stack and the space used to store the current path.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post