Subtree removal game with fibonacci tree

Math Dynamic Programming Tree Binary Tree Game Theory

57.7% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_game_winner(n: i32) -> bool {
    // Sprague-Grundy on Fibonacci tree
    // order(n) has left=order(n-2), right=order(n-1)
    // Grundy number of order(0) = 0 (empty, no moves)
    // Grundy number of order(1) = 1 (single node, one move: remove it)
    // For a tree rooted at r with subtrees L,R:
    //   Removing root: grundy = 0 (game over since we remove root)
    //   Actually the game is: pick any node and remove its subtree.
    //   This is a Green Hackenbush / nim-value game on trees.
    // For Fibonacci tree game, the pattern is: Alice wins iff n % 6 != 1
    // Let me compute: order(1): 1 node. Only move: remove root. Whoever takes root loses.
    //   Alice must take root → Alice loses. Result: false (n=1)
    // order(2): root + left child (order(1)). Alice can take the left child. Bob must take root. Bob loses. true (n=2)
    // order(3): true (given)
    // order(4): Let me think... 
    // Actually the Sprague-Grundy values for Fibonacci trees follow:
    // g(0)=0, g(1)=1, g(n) = g(n-2) XOR g(n-1) XOR ? 
    // This is actually a known result: the Grundy number pattern for this specific game.
    // The game: player picks a non-root node and removes its subtree. Last to move wins (since the person forced to take root loses).
    // Wait actually re-reading: "The player that is forced to delete root loses"
    // So this is a misère-ish game. When only root remains, the current player must delete it and loses.
    // The total number of non-root nodes in order(n) is F(n)-1 where F is Fibonacci count.
    // F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)+1
    // Node counts: 0, 1, 2, 4, 7, 12, 20, 33...
    // But you can remove subtrees, not just single nodes.
    // 
    // Known result: Alice wins iff n % 6 != 1.
    n % 6 != 1
  }
}