Skip to main content
Talentd

Subtree Removal Game with Fibonacci Tree - Solution & Explanation

HardPremiumFree on FleetCodeMathDynamic ProgrammingTreeBinary Tree4 min readAsked at: Sony
Practice this problem

Problem Statement

A Fibonacci tree is a binary tree created using the order function order(n):

  • order(0) is the empty tree.
  • order(1) is a binary tree with only one node.
  • order(n) is a binary tree that consists of a root node with the left subtree as order(n - 2) and the right subtree as order(n - 1).

Alice and Bob are playing a game with a Fibonacci tree with Alice staring first. On each turn, a player selects a node and removes that node and its subtree. The player that is forced to delete root loses.

Given the integer n, return true if Alice wins the game or false if Bob wins, assuming both players play optimally.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

Input: n = 3
Output: true
Explanation:
Alice takes the node 1 in the right subtree.
Bob takes either the 1 in the left subtree or the 2 in the right subtree.
Alice takes whichever node Bob doesn't take.
Bob is forced to take the root node 3, so Bob will lose.
Return true because Alice wins.

Example 2:

Input: n = 1
Output: false
Explanation:
Alice is forced to take the root node 1, so Alice will lose.
Return false because Alice loses.

Example 3:

Input: n = 2
Output: true
Explanation:
Alice takes the node 1.
Bob is forced to take the root node 2, so Bob will lose.
Return true because Alice wins.

 

Constraints:

  • 1 <= n <= 100

Approach Overview

Problem Overview: You are given a tree where players take turns removing valid subtrees. A move is allowed only when the removed subtree size follows Fibonacci constraints derived from a Fibonacci tree structure. The goal is to determine whether the first player has a winning strategy assuming both players play optimally.

Approach 1: Brute Force Game Simulation (Exponential Time, O(n) space)

The most direct idea is to simulate every possible move. At each turn, iterate over all nodes and try removing any subtree whose size forms a valid Fibonacci segment of the current tree. After removing a subtree, recursively evaluate the remaining game state and check if the opponent loses. This essentially explores the full game tree and evaluates win/lose states. The approach quickly becomes infeasible because the number of possible subtree removals grows rapidly, leading to exponential time complexity while using O(n) recursion stack space.

Approach 2: DFS with Fibonacci Decomposition and Game DP (O(n) time, O(n) space)

The optimal strategy relies on properties of Fibonacci trees. Precompute Fibonacci numbers up to n and check whether the tree size belongs to the sequence. Then run a DFS to compute subtree sizes for every node. If the tree size equals F[k], any valid move must split the tree into components of size F[k-1] and F[k-2]. During DFS, track edges where removing that edge creates exactly these two Fibonacci-sized components.

Once such a split is found, recursively evaluate both resulting components as independent games. Use memoization to cache results for subtree sizes to avoid recomputation. If any valid split leads to a position where the opponent loses, the current state is winning. The algorithm combines subtree size computation from tree traversal with memoized decisions from dynamic programming and winning-state evaluation from game theory. Because each node and edge is processed a constant number of times, the total runtime stays O(n) with O(n) auxiliary space.

Recommended for interviews: Interviewers expect the Fibonacci decomposition insight combined with DFS subtree size computation. Starting with brute force demonstrates understanding of the game state, but the optimized approach shows mastery of tree recursion, Fibonacci constraints, and dynamic programming for impartial games.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Game SimulationExponentialO(n)Conceptual understanding of all possible subtree removals
DFS with Fibonacci Decomposition + Game DPO(n)O(n)Optimal approach for large trees using Fibonacci structure

Video Solution

LeetCode 2005: Subtree Removal Game with Fibonacci Tree • AlitaCode • 10 views views

Frequently Asked Questions

Is Subtree Removal Game with Fibonacci Tree easy or hard?
Subtree Removal Game with Fibonacci Tree is classified as a Hard problem. It requires recognizing the Fibonacci decomposition property of the tree and combining DFS traversal with dynamic programming and game theory reasoning.
Subtree Removal Game with Fibonacci Tree Python/Java solution
A typical implementation builds an adjacency list, precomputes Fibonacci numbers, and runs DFS to calculate subtree sizes. During traversal, edges that split the tree into Fibonacci-sized components are identified and recursively evaluated with memoization. The same logic can be implemented in Python, Java, C++, or Go with O(n) complexity.
How to solve Subtree Removal Game with Fibonacci Tree in O(n)?
First precompute Fibonacci numbers up to n and verify that the tree size is a Fibonacci number. Perform a DFS to compute subtree sizes and locate edges that split the tree into F[k-1] and F[k-2] components. Recursively evaluate these components with memoization to determine winning states. Since each node and edge is processed once, the overall complexity is O(n).
What is the best approach for Subtree Removal Game with Fibonacci Tree?
The best approach uses DFS to compute subtree sizes and checks whether the tree can be split according to Fibonacci numbers. Valid splits divide the tree into F[k-1] and F[k-2] components. Using memoized dynamic programming on these components determines whether a position is winning or losing. This approach runs in O(n) time and O(n) space.
Is Subtree Removal Game with Fibonacci Tree asked at Google/Amazon/Meta?
Problems combining tree decomposition, Fibonacci constraints, and game theory frequently appear in interviews at large tech companies such as Google and Meta. They test recursive reasoning, DFS traversal, and understanding of impartial games on graphs or trees.
What data structure is used in Subtree Removal Game with Fibonacci Tree?
The core data structure is a tree represented with adjacency lists. DFS traversal computes subtree sizes, while arrays or hash maps store Fibonacci numbers and memoized game states. This combination enables efficient dynamic programming over the tree structure.
What is the time complexity of Subtree Removal Game with Fibonacci Tree?
The optimal algorithm runs in O(n) time where n is the number of nodes in the tree. Each node is visited during DFS to compute subtree sizes, and each edge is checked at most a constant number of times for Fibonacci splits. The space complexity is O(n) due to recursion and auxiliary arrays.

Ready to solve this problem?

Practice Subtree Removal Game with Fibonacci Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Game of Nim