Sunday, July 23rd

Listing all possible trees is the subject of today's LeetCode problem.

Given a number n, enumerate all possible full binary trees (FBT) with n nodes.  A full binary tree is a tree where every node has either 0 or 2 nodes

Like many tree problems, we can use recursion to find a solution.  We will also use dynamic programming to store intermediate results and avoid duplicate computations

First we declare a hashmap that, for a given value n, stores all possible full binary trees with n nodes

    unordered_map<int, vector<TreeNode*> > memo;

Then we do a few things at the beginning of the function

    vector<TreeNode*> allPossibleFBT(int n) {
        ...
    }

First, since a full binary tree must have an odd number of nodes, we check if n is even

  if(n%2==0) return {};

Then we check the base case as required by recursion.  If n equals 1, then we return an empty node, since that's the only configuration available

    if(n==1) return {new TreeNode(0)};

Third, since we're using dynamic programming, we test is the solution for n nodes has already been found

    if(memo.find(n)!=memo.end()) return memo[n];
 
Now for the meat, we initialize a vector to store results, as well as two variables lcount and rcount.  These last two variables represent the sizes of the left and right subtrees.  lcount starts off equal to 1, and rcount is equal to n-1-lcount, which is the number of nodes less the root node, less the left tree.  

Using left and right subtree sizes, we loop over all possible configuration of sizes for subtrees.  Since a tree can't have an even number of nodes, lcount is incremented by 2 each loop.

    vector<TreeNode*> res;
    int lcount = 1, rcount;
    while(true) {
        rcount=n-1-lcount;
        if(rcount<=0) break;

        ...

        lcount+=2;
    }
        
Now, using recursion, we solve the subproblems of finding all possible full binary trees given the sizes of the left and right subtree

vector<TreeNode*> leftsubtrees = allPossibleFBT(lcount);
    vector<TreeNode*> rightsubtrees = allPossibleFBT(rcount);

So now we vectors that store all possible configurations of FBTs for subtrees of given sides.  How do we create trees from that?  By iterating over all possible right/left subtree combinations, then creating a new TreeNode root that has each left/right combo as a subtree.  Each new root is added to the result vector.

    for(auto lst : leftsubtrees) {
        for(auto rst : rightsubtrees) {
            TreeNode* root = new TreeNode(0, lst, rst);
            res.push_back(root);
        }
    }

Redundant computation may occur repeatedly when right and left subtree sizes have already been solved.  This is mitigated by storing the solution in the memo hashmap, then returning it

     memo[n]=res;
     return memo[n];

That's it.  Challenging problem, good to know how to start ones like these in the future.

Special shout out to user cityofsky for a helpful video

Comments

Post a Comment

Popular posts from this blog

Wednesday, September 20th

Image
 Reduce X to Zero Given an integer array and value x, use elements at the right and left of the array to reduce the x value to zero A collection of windows, by Daderot .  Shared under the Creative Commons Attribution-Share Alike 3.0 Unported License .  No changes made A key observation is that if elements at the ends of the array are used to sum up to a target value x , then elements in a contiguous subarray will equal the total_sum - x .  So we will look for the largest window equal to  total_sum - x Since all elements in the array are positive, then we can solve the problem using 2 pointers that form a sliding window. The general idea is to begin 2 pointers right and left at index 0.  Continue incrementing the right index by 1, adding up the elements it passes into the current_window  sum.  If the sum equals the target value, update the length.  Otherwise, if the sum is greater than the target sum, increment the left index until the window...
Read more

Monday, September 11th

Image
 Groups There are a given number of people, each of whom is assigned to a group.  The number identifier of the group is also its size.  The size of a group may be a multiple of its size, e.g. a group of 3 may have 6 people.  Return the  collection of all groups . Team USA Softball (a group).  Shared by USASoftball , via Wikipedia , distributed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made. This problem is pretty straightforward.  The idea is to create a map (or a vector) keyed by the group, storing an array of individuals belonging to the group. First we create the vector-of-vectors to store our solution, then we initialize a vector of vectors that will store individuals according to their group numbers.  The size of the solution vector is n+1, because contrary to what the beginning of the problem statement said, the indices/group sizes go from 1 to n, according to the stated constraints. vect...
Read more

Tuesday, September 19th

Image
 Find the duplicate number Given an array of integers of length n+1, which contains numbers within the range [1,n], and contains on element that is duplicated at least once, find the duplicate element , considering use of only constant space and no changes to the array "How They Met Themselves" by Dante Rossetti, depicting doppelgängers The problem of finding duplicates is made difficult by the constraints of no modifications to the original array, and use of only constant extra space.  Still, despite these constraints there are still several ways to solve the problem.   Since yesterday's solution involved binary search, we will hone our BS skills by applying it to today's problem The general idea is based on the observation that without duplicates, the number of elements less than or equal an element is equal to the element itself.  E.g., in the collection {1,2,3,4}, the number of elements less than or equal to 2 is 2, less than or equal to 3 is 3, etc.   Howe...
Read more