Ways to Remove Leaves of a Tree - Google Top Interview Questions

Problem Statement :

You are given a binary tree root. 

In one operation you can delete one leaf node in the tree. 

Return the number of different ways there are to delete the whole tree.


0 ≤ n ≤ 100,000

Example 1



root = [1, [2, null, null], [3, [4, null, null], null]]




The three ways to delete are

[2, 4, 3, 1]

[4, 2, 3, 1]

[4, 3, 2, 1]





Solution :


                        Solution in Java :

import java.util.*;

 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
class Solution {
    static long[][] rd = new long[100001][101];
    static final int MODE = 1000000007;
    static {
        for (int i = 0; i < rd.length; ++i) {
            rd[i][0] = 1;
            for (int j = 1; j < i && j < rd[0].length; ++j) {
                rd[i][j] = (rd[i - 1][j - 1] + rd[i - 1][j]) % MODE;
            if (i < rd[0].length)
                rd[i][i] = 1;
    public int solve(Tree root) {
        int[] res = todo(root);
        return res[0];

    private int[] todo(Tree root) {
        if (root == null)
            return new int[] {1, 0};
        int[] l = todo(root.left), r = todo(root.right);
        long t;
        if (l[1] <= r[1]) {
            t = rd[l[1] + r[1]][l[1]];
        } else {
            t = rd[l[1] + r[1]][r[1]];
        t *= l[0] * r[0];
        l[0] = (int) (t % MODE);
        l[1] += r[1] + 1;
        return l;

                        Solution in Python : 
class Solution:
    def solve(self, root):
        def rec(root):  # return (size, number of ways) for current subtree
            if root is None:  # Root is null
                return (0, 1)
            leftsize, leftdp = rec(root.left)
            rightsize, rightdp = rec(root.right)
            return (
                leftsize + rightsize + 1,
                comb(leftsize + rightsize, leftsize) * leftdp * rightdp,

        return rec(root)[1]


Big N

6 months ago
Came up with an exact solution lol. Was thinking it's a elegant solution, so, I should post XD

class Solution:
    def solve(self, root):
        def helper(root):
            if not root:
                return [0, 1]

            leftSize, leftWays, rightSize, rightWays = helper(root.left) + helper(root.right)
            return [ leftSize + rightSize + 1, leftWays * rightWays * math.comb(leftSize + rightSize, leftSize) ]

        return helper(root).pop()

View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →