Is Maximum XOR of Two Non-Overlapping Subtrees easy or hard?

Maximum XOR of Two Non-Overlapping Subtrees is classified as Hard. The difficulty comes from combining multiple concepts: subtree sum computation, enforcing non-overlapping constraints, and using a trie to maximize XOR efficiently. Implementing the postorder logic correctly is the main challenge.

Maximum XOR of Two Non-Overlapping Subtrees Python/Java solution

Implement a DFS to compute subtree sums and process nodes in postorder. Maintain a binary trie that stores sums of already processed subtrees. For each node, query the trie to find the value producing the maximum XOR, update the result, and then insert the current subtree sum. The same logic works in Python, Java, C++, and Go.

How to solve Maximum XOR of Two Non-Overlapping Subtrees in O(n)?

A strict O(n) approach is difficult because maximizing XOR generally requires checking bits using a structure like a trie. The common optimized solution is O(n log V), achieved by computing subtree sums with DFS and querying a binary trie for the best XOR partner. This avoids the O(n²) pair comparisons of brute force.

What is the best approach for Maximum XOR of Two Non-Overlapping Subtrees?

The most efficient approach combines Depth-First Search with a binary trie. DFS computes the sum of every subtree, and nodes are processed in postorder. A trie stores subtree sums that are already completed, allowing you to query the maximum XOR partner in O(log V) time. This yields an overall complexity of O(n log V).

Is Maximum XOR of Two Non-Overlapping Subtrees asked at Google/Amazon/Meta?

Problems combining trees, DFS, and XOR maximization frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test subtree processing, prefix XOR, or trie-based maximum XOR queries. The combination of tree traversal and bitwise optimization makes this a typical hard-level interview question.

What data structure is used in Maximum XOR of Two Non-Overlapping Subtrees?

The key data structure is a binary trie (bitwise prefix tree). It stores subtree sums in binary form so you can efficiently find the value that maximizes XOR with a given sum. The algorithm also relies on Depth-First Search to compute subtree sums and ensure nodes are processed in postorder.

What is the time complexity of Maximum XOR of Two Non-Overlapping Subtrees?

The optimal solution runs in O(n log V) time, where n is the number of nodes and V is the maximum subtree sum value. Each node performs one trie query and one insertion, both taking O(log V) bit operations. Space complexity is also O(n log V) due to the trie structure storing subtree sums.

Description Hints 2 Solution

2479. Maximum XOR of Two Non-Overlapping Subtrees

Hard51.3% acceptance2 companiesPremium elsewhere, free here

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree. The root of the tree is the node labeled 0.

Each node has an associated value. You are given an array values of length n, where values[i] is the value of the i^th node.

Select any two non-overlapping subtrees. Your score is the bitwise XOR of the sum of the values within those subtrees.

Return the maximum possible score you can achieve. If it is impossible to find two nonoverlapping subtrees, return 0.

Note that:

The subtree of a node is the tree consisting of that node and all of its descendants.
Two subtrees are non-overlapping if they do not share any common node.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[2,5]], values = [2,8,3,6,2,5]
Output: 24
Explanation: Node 1's subtree has sum of values 16, while node 2's subtree has sum of values 8, so choosing these nodes will yield a score of 16 XOR 8 = 24. It can be proved that is the maximum possible score we can obtain.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]], values = [4,6,1]
Output: 0
Explanation: There is no possible way to select two non-overlapping subtrees, so we just return 0.

Constraints:

2 <= n <= 5 * 10⁴
edges.length == n - 1
0 <= a_i, b_i < n
values.length == n
1 <= values[i] <= 10⁹
It is guaranteed that edges represents a valid tree.

Asked at 2 companies

Directi Medianet

Topics

Hints open one at a time

Hint 1

Try to build the answer bit by bit from the most significant bit to the least significant.

Hint 2

Use the Trie Data Structure to decide for each bit if it exists in the final answer.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

6
[[0,1],[0,2],[1,3],[1,4],[2,5]]
[2,8,3,6,2,5]

Input

3
[[0,1],[1,2]]
[4,6,1]

Your code is saved on this device.Solution