Skip to main content
Talentd

Maximum XOR of Two Non-Overlapping Subtrees - Solution & Explanation

HardPremiumFree on FleetCodeTreeDepth-First SearchGraphTrie8 min readAsked at: Directi, Medianet
Practice this problem

Problem Statement

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 * 104
  • edges.length == n - 1
  • 0 <= ai, bi < n
  • values.length == n
  • 1 <= values[i] <= 109
  • It is guaranteed that edges represents 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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree Pair CheckO(n²)O(n)Useful for understanding subtree relationships or when n is very small
DFS + Binary Trie on Subtree SumsO(n log V)O(n log V)General optimal solution for large trees where fast XOR maximization is required

Video Solution

Non-Overlapping Intervals - Leetcode 435 - Python • NeetCode • 134,480 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum XOR of Two Non-Overlapping Subtrees with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II