LeetCode 2479: Maximum XOR of Two Non-Overlapping Subtrees Solution

Master LeetCode problem 2479 (Maximum XOR of Two Non-Overlapping Subtrees), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2479. Maximum XOR of Two Non-Overlapping Subtrees

Hard

Tree Depth-First Search Graph Trie

Problem Explanation

Explanation

To solve this problem, we can use a recursive approach to find the maximum XOR of two non-overlapping subtrees at each node. We will calculate the XOR of the subtree rooted at each node and compare it with the XOR of the other subtrees in the tree. At each node, we will consider two cases: either the left subtree or the right subtree is included in the XOR calculation.

We will traverse the tree in a post-order manner to calculate the XOR values of all subtrees. At each node, we will calculate the XOR values of the left and right subtrees and store them. Then, we will recursively find the maximum XOR of two non-overlapping subtrees for the current node.

Finally, we will return the maximum XOR value found during the traversal.

Algorithm:

Define a helper function dfs to calculate the XOR values of subtrees and find the maximum XOR of two non-overlapping subtrees at each node.
Initialize a global variable maxXOR to store the maximum XOR value found.
Traverse the tree in a post-order manner.
At each node, recursively calculate the XOR values of left and right subtrees.
Calculate the XOR value of the current subtree by XORing the subtree's value with the XOR values of left and right subtrees.
Update the maxXOR if a greater value is found.
Return the XOR value of the current subtree.
Return the maxXOR value as the final result.

Time Complexity:

The time complexity of this approach is O(N), where N is the number of nodes in the binary tree.

Space Complexity:

The space complexity is O(N) due to the recursive stack space used during traversal.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    int maxXOR = 0;
    
    public int getMaxXOR(TreeNode root) {
        postOrder(root);
        return maxXOR;
    }
    
    private int postOrder(TreeNode node) {
        if (node == null) return 0;
        
        int leftXOR = postOrder(node.left);
        int rightXOR = postOrder(node.right);
        
        int currXOR = leftXOR ^ rightXOR ^ node.val;
        
        maxXOR = Math.max(maxXOR, Math.max(currXOR, Math.max(leftXOR, rightXOR)));
        
        return currXOR;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2479 (Maximum XOR of Two Non-Overlapping Subtrees)?

This page provides optimized solutions for LeetCode problem 2479 (Maximum XOR of Two Non-Overlapping Subtrees) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2479 (Maximum XOR of Two Non-Overlapping Subtrees)?

The time complexity for LeetCode 2479 (Maximum XOR of Two Non-Overlapping Subtrees) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2479 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2479 in Java, C++, or Python.

Back to LeetCode Solutions