Given a tree with N distinct nodes from the range [1, n] and two integers x and val. The task is to find the maximum value of any node when XORed with x on the path from the root to val.
Examples:
Input: val = 6, x = 4
1
/ \
2 3
/ \
4 5
/
6
Output: 7
the path is 1 -> 3 -> 5 -> 6
1 ^ 4 = 5
3 ^ 4 = 7
5 ^ 4 = 1
6 ^ 4 = 2
Maximum is 7
Input: val = 4, x = 1
1
/ \
2 3
/
4
Output: 5
Approach:
- An optimized solution to the problem is to create a parent array to store the parent of each of the node.
- Start from the given node and keep on going up in the tree using the parent array (this will be helpful when answering a number of queries as only the nodes on the path will be traversed). Take the xor with x of all the nodes in the path till root.
- The maximum xor calculated for the path is the answer.
Below is the implementation of the above approach:
C++14
// CPP implementation of the approach#include <bits/stdc++.h>using namespace std;// Tree nodeclass Node{public: int data; Node *left, *right; Node(int data) { this->data = data; this->left = NULL; this->right = NULL; }};// Recursive function to update// the parent array such that parent[i]// stores the parent of ivoid updateParent(int *parent, Node *node){ // If node is null then return if (node == NULL) return; // If left child of the node is not // null then set node as the parent // of its left child if (node->left != NULL) parent[node->left->data] = node->data; // If right child of the node is not // null then set node as the parent // of its right child if (node->right != NULL) parent[node->right->data] = node->data; // Recursive call for the // children of current node updateParent(parent, node->left); updateParent(parent, node->right);}// Function to return the maximum value// of a node on the path from root to val// when Xored with xint getMaxXor(Node *root, int n, int val, int x){ // Create the parent array int *parent = new int[n + 1]; updateParent(parent, root); // Initialize max with x XOR val int maximum = x ^ val; // Get to the parent of val val = parent[val]; // 0 is the parent of the root while (val != 0) { // Update maximum maximum = max(maximum, x ^ val); // Get one level up the tree val = parent[val]; } return maximum;}// Driver Codeint main(){ int n = 6; Node *root; root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->right = new Node(5); root->right->right->left = new Node(6); int val = 6, x = 4; cout << getMaxXor(root, n, val, x) << endl; return 0;}// This code is contributed by// sanjeev2552 |
Java
// Java implementation of the approachpublic class GFG { // Tree node static class Node { int data; Node left, right; Node(int data) { this.data = data; left = null; right = null; } } // Recursive function to update // the parent array such that parent[i] // stores the parent of i static void updateParent(int parent[], Node node) { // If node is null then return if (node == null) return; // If left child of the node is not // null then set node as the parent // of its left child if (node.left != null) parent[node.left.data] = node.data; // If right child of the node is not // null then set node as the parent // of its right child if (node.right != null) parent[node.right.data] = node.data; // Recursive call for the // children of current node updateParent(parent, node.left); updateParent(parent, node.right); } // Function to return the maximum value // of a node on the path from root to val // when Xored with x static int getMaxXor(Node root, int n, int val, int x) { // Create the parent array int parent[] = new int[n + 1]; updateParent(parent, root); // Initialize max with x XOR val int max = x ^ val; // Get to the parent of val val = parent[val]; // 0 is the parent of the root while (val != 0) { // Update maximum max = Math.max(max, x ^ val); // Get one level up the tree val = parent[val]; } return max; } // Driver code public static void main(String[] args) { int n = 6; Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.right = new Node(5); root.right.right.left = new Node(6); int val = 6, x = 4; System.out.println(getMaxXor(root, n, val, x)); }} |
Python3
# Python3 implementation of the approach# Tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None # Recursive function to update# the parent array such that parent[i]# stores the parent of idef updateParent(parent, node): # If node is None then return if (node == None): return parent # If left child of the node is not # None then set node as the parent # of its left child if (node.left != None): parent[node.left.data] = node.data # If right child of the node is not # None then set node as the parent # of its right child if (node.right != None): parent[node.right.data] = node.data # Recursive call for the # children of current node parent = updateParent(parent, node.left) parent = updateParent(parent, node.right) return parent# Function to return the maximum value# of a node on the path from root to val# when Xored with xdef getMaxXor(root, n, val, x): # Create the parent array parent = [0]*(n + 1) parent=updateParent(parent, root) # Initialize max with x XOR val maximum = x ^ val # Get to the parent of val val = parent[val] # 0 is the parent of the root while (val != 0): # Update maximum maximum = max(maximum, x ^ val) # Get one level up the tree val = parent[val] return maximum# Driver Coden = 6root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.right.right = Node(5)root.right.right.left = Node(6)val = 6x = 4print( getMaxXor(root, n, val, x) )# This code is contributed by Arnab Kundu |
C#
// C# implementation of the approach using System;class GFG{ // Tree node public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = null; right = null; } } // Recursive function to update // the parent array such that parent[i] // stores the parent of i static void updateParent(int []parent, Node node) { // If node is null then return if (node == null) return; // If left child of the node is not // null then set node as the parent // of its left child if (node.left != null) parent[node.left.data] = node.data; // If right child of the node is not // null then set node as the parent // of its right child if (node.right != null) parent[node.right.data] = node.data; // Recursive call for the // children of current node updateParent(parent, node.left); updateParent(parent, node.right); } // Function to return the maximum value // of a node on the path from root to val // when Xored with x static int getMaxXor(Node root, int n, int val, int x) { // Create the parent array int []parent = new int[n + 1]; updateParent(parent, root); // Initialize max with x XOR val int max = x ^ val; // Get to the parent of val val = parent[val]; // 0 is the parent of the root while (val != 0) { // Update maximum max = Math.Max(max, x ^ val); // Get one level up the tree val = parent[val]; } return max; } // Driver code public static void Main(String[] args) { int n = 6; Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.right = new Node(5); root.right.right.left = new Node(6); int val = 6, x = 4; Console.WriteLine(getMaxXor(root, n, val, x)); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of above approach// Tree nodeclass Node{ constructor(data) { this.left = null; this.right = null; this.data = data; }}// Recursive function to update// the parent array such that parent[i]// stores the parent of ifunction updateParent(parent, node){ // If node is null then return if (node == null) return; // If left child of the node is not // null then set node as the parent // of its left child if (node.left != null) parent[node.left.data] = node.data; // If right child of the node is not // null then set node as the parent // of its right child if (node.right != null) parent[node.right.data] = node.data; // Recursive call for the // children of current node updateParent(parent, node.left); updateParent(parent, node.right);}// Function to return the maximum value// of a node on the path from root to val// when Xored with xfunction getMaxXor(root, n, val, x){ // Create the parent array let parent = new Array(n + 1); parent.fill(0); updateParent(parent, root); // Initialize max with x XOR val let max = x ^ val; // Get to the parent of val val = parent[val]; // 0 is the parent of the root while (val != 0) { // Update maximum max = Math.max(max, x ^ val); // Get one level up the tree val = parent[val]; } return max;}// Driver codelet n = 6;let root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.right.right = new Node(5);root.right.right.left = new Node(6);let val = 6, x = 4;document.write(getMaxXor(root, n, val, x));// This code is contributed by divyeshrabadiya07</script> |
Output:
7
Time Complexity: O(N)
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!
