Watch 10 video solutions for Maximum XOR of Two Non-Overlapping Subtrees, a hard level problem involving Tree, Depth-First Search, Graph. This walkthrough by NeetCode has 134,480 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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] <= 109edges represents a valid tree.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.
| 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 |