Skip to main content

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;
    
    path.add(node.data);
    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;
        }
        // Add path element
        path.add(point.data);
        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;
		}
		// Add path element
		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;
		}
		// Add path element
		path.Add(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.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;
		}
		// Add path element
		$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;
		}
		// Add path element
		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
		
		#  Add path element
		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_reader :data, :left, :right
	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_reader :root, :count
	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

		#  Add path element
		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;
		}
		// Add path element
		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;
		}
		// Add path element
		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;
		}
		// Add path element
		path.add(point.data);
		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.

Last updated on by Kalkicode




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.

New Comment