LeetCode 2479 - Maximum XOR of Two Non-Overlapping Subtrees

This problem gives us a rooted tree with n nodes, rooted at node 0. Every node has a numeric value, and the sum of a subtree is defined as the sum of all node values inside that subtree, including the root of the subtree and all descendants.

leetcodehardtreedepth-first-searchgraph-theorytrie

LeetCode Problem 2479

Difficulty: 🔴 Hard
Topics: Tree, Depth-First Search, Graph Theory, Trie

Solution

Problem Understanding

This problem gives us a rooted tree with n nodes, rooted at node 0. Every node has a numeric value, and the sum of a subtree is defined as the sum of all node values inside that subtree, including the root of the subtree and all descendants.

We are asked to choose two subtrees that do not overlap, meaning they share no nodes at all. For every valid pair of non-overlapping subtrees, we compute:

$$\text{subtreeSum}_1 \oplus \text{subtreeSum}_2$$

where ⊕ is the bitwise XOR operator.

Our goal is to maximize this XOR value.

The input consists of:

  • n, the number of nodes
  • edges, describing the undirected tree
  • values, the value assigned to each node

Because the tree is rooted at 0, every node defines exactly one subtree, namely itself and all descendants reachable downward from it.

The constraints are extremely important:

  • n can be as large as 5 * 10^4
  • subtree sums can become very large because node values can reach 10^9
  • a naive pairwise comparison of all subtree pairs would be too slow

The main challenge is efficiently determining:

  1. The subtree sum for every node
  2. Whether two subtrees overlap
  3. The maximum XOR among all valid pairs

Several edge cases are important:

  • A chain-like tree may make recursion depth dangerous in Python
  • There may be no two disjoint subtrees at all, such as a path of length 2
  • Large subtree sums require 64-bit integer handling
  • Two sibling subtrees are always non-overlapping
  • Ancestor-descendant subtree pairs always overlap and must not be considered

The key difficulty is efficiently checking non-overlap while also maximizing XOR.

Approaches

Brute Force Approach

The brute force solution begins by computing the subtree sum for every node.

After that, we consider every pair of nodes (u, v) and determine whether their subtrees overlap. Two subtrees overlap if one node is an ancestor of the other.

If they do not overlap, we compute:

$$\text{subtreeSum}[u] \oplus \text{subtreeSum}[v]$$

and track the maximum value.

To determine ancestor relationships efficiently, we can run a DFS Euler tour and record entry and exit times:

  • u is ancestor of v if:

$$tin[u] \le tin[v] \le tout[u]$$

Even with efficient overlap checking, there are still O(n^2) subtree pairs. With n = 5 * 10^4, this becomes far too slow.

Optimal Approach

The key insight is that XOR maximization problems are often solved using a binary trie.

If we process subtree sums in a careful DFS order, we can ensure that the trie only contains subtree sums from nodes whose subtrees do not overlap with the current node.

The important observation is:

  • When exploring a node's children, previously processed sibling subtrees are guaranteed to be disjoint
  • Descendant subtrees overlap and therefore must not be inserted too early

We perform a DFS and process children one at a time.

For each child subtree:

  1. Query all subtree sums inside this child against sums already stored in the trie
  2. The trie contains only subtree sums from previously completed sibling subtrees
  3. Therefore every queried pair is guaranteed non-overlapping
  4. After querying, insert all subtree sums from this child into the trie

This avoids explicit overlap checks entirely.

The trie allows us to find the maximum XOR partner for a number in O(log MAX_VALUE) time.

Since subtree sums fit within roughly 46 bits:

$$5 \times 10^4 \times 10^9 = 5 \times 10^{13}$$

each trie operation costs about 46 steps.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Checks every subtree pair
Optimal O(n log M) O(n log M) Uses DFS ordering and binary trie

Here, M is the maximum subtree sum value.

Algorithm Walkthrough

Step 1: Build the Tree

Convert the edge list into an adjacency list.

This allows efficient DFS traversal from the root.

Step 2: Compute All Subtree Sums

Run a DFS starting from node 0.

For each node:

  1. Start with its own value
  2. Recursively compute sums for all children
  3. Add child sums into the current sum
  4. Store the result in subtree_sum[node]

At the end, every node knows the total sum of its subtree.

Step 3: Create a Binary Trie

The trie stores binary representations of subtree sums.

Each trie node contains:

  • child for bit 0
  • child for bit 1

To maximize XOR:

  • for each bit, we prefer taking the opposite bit if available

This greedy bit choice maximizes the XOR value.

Step 4: DFS Again to Process Non-Overlapping Subtrees

We now perform another DFS.

For a node:

  1. Process children one by one
  2. Before inserting a child subtree into the trie, query every subtree sum inside that child against the current trie
  3. The trie contains only completed sibling subtrees from earlier children
  4. Therefore every XOR candidate is valid

After querying:

  • insert every subtree sum from that child into the trie

This incremental ordering guarantees non-overlap automatically.

Step 5: Query Maximum XOR

For every subtree sum:

  1. Walk through trie bits from highest to lowest
  2. Prefer opposite bits whenever possible
  3. Construct the maximum XOR value greedily

Update the global answer whenever a larger XOR is found.

Step 6: Return the Final Answer

If no valid pair exists, the answer remains 0.

Otherwise return the maximum XOR found.

Why it works

The correctness comes from the DFS processing order.

When processing a child subtree, the trie contains subtree sums only from previously completed sibling subtrees. Sibling subtrees in a tree are always disjoint because they belong to different branches.

Since descendant subtrees are not inserted until after querying, overlapping ancestor-descendant pairs are never considered.

The binary trie guarantees that for every subtree sum, we efficiently find the inserted subtree sum that maximizes XOR.

Therefore every candidate is valid, and the maximum among all valid candidates is returned.

Python Solution

from typing import List
import sys

sys.setrecursionlimit(1 << 20)

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.HIGH_BIT = 50

    def insert(self, num: int) -> None:
        node = self.root

        for bit in range(self.HIGH_BIT, -1, -1):
            current = (num >> bit) & 1

            if current not in node.children:
                node.children[current] = TrieNode()

            node = node.children[current]

    def query(self, num: int) -> int:
        node = self.root

        if not node.children:
            return 0

        result = 0

        for bit in range(self.HIGH_BIT, -1, -1):
            current = (num >> bit) & 1
            opposite = 1 - current

            if opposite in node.children:
                result |= (1 << bit)
                node = node.children[opposite]
            else:
                node = node.children[current]

        return result

class Solution:
    def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        subtree_sum = [0] * n
        subtree_nodes = [[] for _ in range(n)]

        def compute_subtree(node: int, parent: int) -> int:
            total = values[node]
            subtree_nodes[node].append(node)

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                total += compute_subtree(neighbor, node)
                subtree_nodes[node].extend(subtree_nodes[neighbor])

            subtree_sum[node] = total
            return total

        compute_subtree(0, -1)

        trie = Trie()
        answer = 0

        def process(node: int, parent: int) -> None:
            nonlocal answer

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                for descendant in subtree_nodes[neighbor]:
                    current_sum = subtree_sum[descendant]
                    answer = max(answer, trie.query(current_sum))

                for descendant in subtree_nodes[neighbor]:
                    trie.insert(subtree_sum[descendant])

                process(neighbor, node)

        process(0, -1)

        return answer

The implementation begins by constructing the adjacency list representation of the tree.

The first DFS computes subtree sums. During this traversal, we also collect all descendants belonging to each subtree. This allows later iteration through every subtree sum inside a branch.

The trie implementation supports two operations:

  • insert, which stores a subtree sum bit-by-bit
  • query, which greedily searches for the number producing maximum XOR

The second DFS is where the non-overlap logic appears.

For every child subtree:

  1. Query all subtree sums against the existing trie
  2. Insert the subtree sums afterward

This ordering is essential because it ensures the trie only contains subtree sums from previously completed sibling branches.

The answer is updated continuously whenever a larger XOR value is found.

Go Solution

package main

type TrieNode struct {
	children [2]*TrieNode
}

type Trie struct {
	root    *TrieNode
	highBit int
}

func NewTrie() *Trie {
	return &Trie{
		root:    &TrieNode{},
		highBit: 50,
	}
}

func (t *Trie) Insert(num int64) {
	node := t.root

	for bit := t.highBit; bit >= 0; bit-- {
		current := (num >> bit) & 1

		if node.children[current] == nil {
			node.children[current] = &TrieNode{}
		}

		node = node.children[current]
	}
}

func (t *Trie) Query(num int64) int64 {
	node := t.root

	if node.children[0] == nil && node.children[1] == nil {
		return 0
	}

	var result int64 = 0

	for bit := t.highBit; bit >= 0; bit-- {
		current := (num >> bit) & 1
		opposite := 1 - current

		if node.children[opposite] != nil {
			result |= (1 << bit)
			node = node.children[opposite]
		} else {
			node = node.children[current]
		}
	}

	return result
}

func maxXor(n int, edges [][]int, values []int) int64 {
	graph := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	subtreeSum := make([]int64, n)
	subtreeNodes := make([][]int, n)

	var computeSubtree func(int, int) int64

	computeSubtree = func(node int, parent int) int64 {
		total := int64(values[node])
		subtreeNodes[node] = append(subtreeNodes[node], node)

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			total += computeSubtree(neighbor, node)
			subtreeNodes[node] = append(subtreeNodes[node], subtreeNodes[neighbor]...)
		}

		subtreeSum[node] = total
		return total
	}

	computeSubtree(0, -1)

	trie := NewTrie()
	var answer int64 = 0

	var process func(int, int)

	process = func(node int, parent int) {
		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			for _, descendant := range subtreeNodes[neighbor] {
				currentSum := subtreeSum[descendant]
				answer = max64(answer, trie.Query(currentSum))
			}

			for _, descendant := range subtreeNodes[neighbor] {
				trie.Insert(subtreeSum[descendant])
			}

			process(neighbor, node)
		}
	}

	process(0, -1)

	return answer
}

func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

The Go implementation closely follows the Python logic.

The main difference is explicit use of int64 because subtree sums may exceed 32-bit integer limits.

Go arrays are fixed-size, so trie children are stored as:

children [2]*TrieNode

instead of Python dictionaries.

Recursive DFS behavior is otherwise identical.

Worked Examples

Example 1

Input:

n = 6
edges = [[0,1],[0,2],[1,3],[1,4],[2,5]]
values = [2,8,3,6,2,5]

Step 1: Compute Subtree Sums

Node Subtree Nodes Sum
3 [3] 6
4 [4] 2
1 [1,3,4] 16
5 [5] 5
2 [2,5] 8
0 [0,1,2,3,4,5] 26

Step 2: Process Children of Root

Initially trie is empty.

Process child 1:

  • Query subtree sums {16, 6, 2}
  • Trie empty, no updates
  • Insert {16, 6, 2}

Trie now contains:

16, 6, 2

Process child 2:

  • Query 8

$$8 \oplus 16 = 24$$

  • Query 5

$$5 \oplus 16 = 21$$

Maximum becomes 24.

Insert {8, 5}.

Final answer:

24

Example 2

Input:

n = 3
edges = [[0,1],[1,2]]
values = [4,6,1]

Subtree sums:

Node Sum
2 1
1 7
0 11

Every subtree overlaps with every other subtree because the tree is a chain.

No valid pair exists.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log M) Each subtree sum is inserted and queried once
Space O(n log M) Trie stores binary representation of subtree sums

Here, M is the maximum subtree sum value.

Each trie operation takes approximately 51 bit operations because subtree sums fit within 51 bits.

Since every node participates in one insertion and one query, the total complexity becomes linear in the number of nodes times the bit width.

Test Cases

from typing import List

sol = Solution()

# Example 1
assert sol.maxXor(
    6,
    [[0,1],[0,2],[1,3],[1,4],[2,5]],
    [2,8,3,6,2,5]
) == 24  # standard branching example

# Example 2
assert sol.maxXor(
    3,
    [[0,1],[1,2]],
    [4,6,1]
) == 0  # no non-overlapping subtrees

# Small balanced tree
assert sol.maxXor(
    3,
    [[0,1],[0,2]],
    [1,2,3]
) == 1  # subtree sums 2 and 3 -> 2 XOR 3 = 1

# Single valid pair
assert sol.maxXor(
    4,
    [[0,1],[1,2],[1,3]],
    [1,2,4,8]
) == 12  # 4 XOR 8

# Large values
assert sol.maxXor(
    3,
    [[0,1],[0,2]],
    [10**9,10**9,10**9]
) == 0  # equal subtree sums

# Deep chain
assert sol.maxXor(
    5,
    [[0,1],[1,2],[2,3],[3,4]],
    [1,2,3,4,5]
) == 0  # all subtrees overlap

# Multiple siblings
assert sol.maxXor(
    5,
    [[0,1],[0,2],[0,3],[0,4]],
    [1,2,4,8,16]
) == 24  # 8 XOR 16

# Uneven tree
assert sol.maxXor(
    7,
    [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6]],
    [5,1,7,2,3,4,6]
) >= 0  # general correctness stress case
Test Why
Example 1 Validates standard branching structure
Example 2 Verifies handling when no valid pair exists
Small balanced tree Confirms sibling subtree handling
Single valid pair Tests simple XOR maximization
Large values Ensures large integer correctness
Deep chain Verifies overlap exclusion
Multiple siblings Tests many disjoint candidates
Uneven tree General stress and traversal validation

Edge Cases

Chain-Like Trees

A linear chain is an important edge case because every subtree overlaps with every other subtree. There are no sibling branches, so no two subtrees can be disjoint.

A naive implementation might incorrectly compare descendant subtrees and produce invalid answers. The DFS ordering in this solution prevents that because descendant subtrees are never simultaneously present in the trie during querying.

Very Large Subtree Sums

Since node values may reach 10^9 and there can be 5 * 10^4 nodes, subtree sums may become extremely large.

The implementation handles this safely by:

  • using Python integers, which are arbitrary precision
  • using int64 in Go

The trie uses 51 bits to safely represent all possible sums.

Trees With Only One Branching Point

Consider a tree where only one node has two children and the rest form chains.

This can easily expose bugs where the trie accidentally contains overlapping descendant subtrees.

The solution avoids this by inserting subtree sums only after all queries for the current sibling subtree are completed. This guarantees that only already-finished sibling branches exist in the trie.