Maximum XOR of Two Non-Overlapping Subtrees solution and explanation
The problem
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] = [ai, bi] indicates that there is an edge between nodes ai and bi 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 ith 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 * 104edges.length == n - 10 <= ai, bi < nvalues.length == n1 <= values[i] <= 109- It is guaranteed that
edgesrepresents a valid tree.
Approach overview
Problem Overview: Given a tree where each node has a value, compute the sum of every subtree and choose two non-overlapping subtrees whose sums produce the maximum XOR. Two subtrees are non-overlapping if neither is inside the other.
Approach 1: Brute Force Subtree Comparison (O(n²) time, O(n) space)
Run a Depth-First Search to compute the sum of every subtree and record entry/exit times from an Euler tour. The timestamps let you check whether two nodes belong to overlapping subtrees (ancestor–descendant relationship). After collecting all subtree sums, iterate over every pair of nodes and skip pairs where one subtree contains the other. For valid pairs, compute sum[i] ^ sum[j] and track the maximum. This approach is straightforward but requires checking roughly n² pairs, which becomes too slow for large trees.
Approach 2: DFS + Binary Trie on Subtree Sums (O(n log V) time, O(n log V) space)
The optimized method still begins with a DFS to compute subtree sums. Process nodes in postorder so that a node is handled only after all its children are finished. Maintain a binary trie containing subtree sums of nodes whose subtrees have already been completely processed. Because a parent finishes after its children, inserting sums only after processing a node guarantees that no ancestor of the current node exists in the trie. That automatically enforces the non‑overlapping constraint.
For each node, once its subtree sum is known, query the trie to find the value that maximizes XOR with this sum. Standard maximum-XOR trie logic walks from the most significant bit to the least, preferring the opposite bit when available. Update the global answer with the best XOR result. After the query, insert the current subtree sum into the trie so future nodes can pair with it. The trie search and insertion both take O(log V), where V is the maximum possible subtree sum.
Recommended for interviews: The DFS + Trie solution is what interviewers expect for a hard tree/XOR problem. Explaining the brute-force pair check shows you understand subtree relationships, but implementing the trie optimization demonstrates strong command of tree traversal and bitwise data structures.
Solution
class Trie:
def __init__(self):
self.children = [None] * 2
def insert(self, x):
node = self
for i in range(47, -1, -1):
v = (x >> i) & 1
if node.children[v] is None:
node.children[v] = Trie()
node = node.children[v]
def search(self, x):
node = self
res = 0
for i in range(47, -1, -1):
v = (x >> i) & 1
if node is None:
return res
if node.children[v ^ 1]:
res = res << 1 | 1
node = node.children[v ^ 1]
else:
res <<= 1
node = node.children[v]
return res
class Solution:
def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:
def dfs1(i, fa):
t = values[i]
for j in g[i]:
if j != fa:
t += dfs1(j, i)
s[i] = t
return t
def dfs2(i, fa):
nonlocal ans
ans = max(ans, tree.search(s[i]))
for j in g[i]:
if j != fa:
dfs2(j, i)
tree.insert(s[i])
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
s = [0] * n
dfs1(0, -1)
ans = 0
tree = Trie()
dfs2(0, -1)
return ansclass Trie {
Trie[] children = new Trie[2];
void insert(long x) {
Trie node = this;
for (int i = 47; i >= 0; --i) {
int v = (int) (x >> i) & 1;
if (node.children[v] == null) {
node.children[v] = new Trie();
}
node = node.children[v];
}
}
long search(long x) {
Trie node = this;
long res = 0;
for (int i = 47; i >= 0; --i) {
int v = (int) (x >> i) & 1;
if (node == null) {
return res;
}
if (node.children[v ^ 1] != null) {
res = res << 1 | 1;
node = node.children[v ^ 1];
} else {
res <<= 1;
node = node.children[v];
}
}
return res;
}
}
class Solution {
private List<Integer>[] g;
private int[] vals;
private long[] s;
private Trie tree;
private long ans;
public long maxXor(int n, int[][] edges, int[] values) {
g = new List[n];
s = new long[n];
vals = values;
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
g[b].add(a);
}
dfs1(0, -1);
tree = new Trie();
dfs2(0, -1);
return ans;
}
private void dfs2(int i, int fa) {
ans = Math.max(ans, tree.search(s[i]));
for (int j : g[i]) {
if (j != fa) {
dfs2(j, i);
}
}
tree.insert(s[i]);
}
private long dfs1(int i, int fa) {
long t = vals[i];
for (int j : g[i]) {
if (j != fa) {
t += dfs1(j, i);
}
}
s[i] = t;
return t;
}
}using ll = long long;
class Trie {
public:
vector<Trie*> children;
string v;
Trie()
: children(2) {}
void insert(ll x) {
Trie* node = this;
for (int i = 47; ~i; --i) {
int v = (x >> i) & 1;
if (!node->children[v]) node->children[v] = new Trie();
node = node->children[v];
}
}
ll search(ll x) {
Trie* node = this;
ll res = 0;
for (int i = 47; ~i; --i) {
if (!node) return res;
int v = (x >> i) & 1;
if (node->children[v ^ 1]) {
res = res << 1 | 1;
node = node->children[v ^ 1];
} else {
res <<= 1;
node = node->children[v];
}
}
return res;
}
};
class Solution {
public:
long long maxXor(int n, vector<vector<int>>& edges, vector<int>& values) {
vector<vector<int>> g(n);
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<ll> s(n);
function<ll(int, int)> dfs1 = [&](int i, int fa) -> ll {
ll t = values[i];
for (int j : g[i]) {
if (j != fa) t += dfs1(j, i);
}
s[i] = t;
return t;
};
dfs1(0, -1);
Trie tree;
ll ans = 0;
function<void(int, int)> dfs2 = [&](int i, int fa) {
ans = max(ans, tree.search(s[i]));
for (int j : g[i]) {
if (j != fa) {
dfs2(j, i);
}
}
tree.insert(s[i]);
};
dfs2(0, -1);
return ans;
}
};type Trie struct {
children [2]*Trie
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(x int) {
node := this
for i := 47; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (this *Trie) search(x int) int {
node := this
res := 0
for i := 47; i >= 0; i-- {
v := (x >> i) & 1
if node == nil {
return res
}
if node.children[v^1] != nil {
res = res<<1 | 1
node = node.children[v^1]
} else {
res <<= 1
node = node.children[v]
}
}
return res
}
func maxXor(n int, edges [][]int, values []int) int64 {
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
s := make([]int, n)
var dfs1 func(i, fa int) int
dfs1 = func(i, fa int) int {
t := values[i]
for _, j := range g[i] {
if j != fa {
t += dfs1(j, i)
}
}
s[i] = t
return t
}
dfs1(0, -1)
ans := 0
tree := newTrie()
var dfs2 func(i, fa int)
dfs2 = func(i, fa int) {
ans = max(ans, tree.search(s[i]))
for _, j := range g[i] {
if j != fa {
dfs2(j, i)
}
}
tree.insert(s[i])
}
dfs2(0, -1)
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Pair Check | O(n²) | O(n) | Useful for understanding subtree relationships or when n is very small |
| DFS + Binary Trie on Subtree Sums | O(n log V) | O(n log V) | General optimal solution for large trees where fast XOR maximization is required |
Frequently asked questions
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.