Actually we can remove all the even numbers from the for loops and input as well. My code got 98% better runtime and 83% better mem. utilization than the rest of the entries. if n % 2 == 0: return [] dp = {0 : [], 1 : [TreeNode()]}
def backtrack(n): if n in dp: return dp[n]
res = [] for l in range(1,n,2): r = n - 1 - l leftTrees,rightTrees = backtrack(l),backtrack(r) for lt in leftTrees: for rt in rightTrees: res.append(TreeNode(0,lt,rt)) dp[n] = res return dp[n]
@NeetCode: I guess at 8:20 what you mean to say is to iterate from 1 to n-1. Because the left should have at least 1 left node. Thank you for the solution. Its very easy to follow.
I think the case where n = 2 is handled in the nested for loop where if either of the leftSubtree and rightSubtree lists is empty, there would be no t1 or t2 to append to the result, therefore it will return an empty result.
@@kevinnguyen1706 hi, I am very confused about why do we need to put the nested loop under the first loop (for l in range(n)), I mean when we go through the first loop, we have the number of nodes on left and right, and after that we use nested loop to build up the tree?
If we do not consider n cannot be even, it will lead "time limit exceeded".Better to fix it, should be like below: def allPossibleFBT(self, n): # check if n is even, there will be no possible to assemble FBT. if not n % 2: return [] dp = {0: [], 1: [TreeNode(0)]} def backtrack(n): if n in dp: return dp[n] res = [] # As drawing, L should be 1 at least, if L is 0, it won't be an FBT, And the largest L should be (n - 2). # For avoiding n is even, we need to loop it by 2 numbers. for l in range(1, n - 1, 2): r = n - 1 - l leftTrees, rightTrees = backtrack(l), backtrack(r) for t1 in leftTrees: for t2 in rightTrees: res.append(TreeNode(0, t1, t2)) dp[n] = res return dp[n] return backtrack(n)
But how does this guarantee that we can have a FBT？ If we let left go from 0 - n-1, does this mean that a blank left subtree(not a BST) is accepted? First we know that a even number will return None as some friends. In this case I think the range of left should be range(1, n, 2) because we don't want either of the subtree to be empty and we don't want the even ones.
leftTrees and rightTrees makes a tree even if each gets an even number of nodes. Now we know we cannot make a complete tree if there are even number of nodes. Not sure how those trees with even number of nodes are getting removed from the answer
thx for the video one thing to note: this is just plain old recursion, there is no real backtracking going on here (i.e we dont manipulate a shared datastructure and then revert the change as we unwind from recursion),
hi, I am very confused about why do we need to put the nested loop under the first loop (for l in range(n)), I mean when we go through the first loop, we have the number of nodes on left and right, and after that we use nested loop to build up the tree?
Nested inner loop is required to get all the combinations of the possible trees. Take n=7 for an example. Let's run through the recursion steps. In every step I will take only the ideal choices(I will ignore the choices that will return an empty list, means no reslut), thats how I will be able to explain you the process. So (1st recursion call), lets assume- left will have (0,1,2,3,4,5,6) right will have (5,4,3,2,1,0) choices left = 5 right= 1 now right will return immediately with a subtree having left and right child null and root value as 0-->[0,null,null] (step under consideration) ---->Our recursion will run for left=5. Again left will have (0,1,2,3,4) right will have (3,2,1,0) choices. if we take left - 3, right =1and run further through the recursion taking ideal choices(which will be left=1, right=1 in the subsequent setp), the this recusrion call will return return with subtree [0,0,0] So this call will add [0,0,0,0,0,null,null] to the res array. Outer for loop for (step under consideration) has not finished yet, there is one more ideal choice, left =1 (returns with a subtree [0,null.null]) right = 3 (return with a subtree [0,0,0] So this call will add [0,0,0,null,null,0,0] to the res array. Now comming back to the (1st recursion call) left = 5 --> returned( [ [0,0,0,null,null,0,0] , [0,0,0,0,0,null,null] ] right= 1--> returned [0,null,null] Inner for loops will run now and generate two unique full binary trees. [ [0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0] ] You can use a tree visualizer for better visualization of the trees returned in each step. eniac00.github.io/btv/
The recursion calls return the possibilities for left and right, but when calculating the overall numbers of possible ways, these left and right possibilities' combinations must be considered as well, that's why
Vey nice remark n needs to be always an odd number so n-1 can be an even, otherwise the result is an empty list (n % 2 == 0), and so if n-1 is even it can be written as the sum of 2 odds integers. And this remark speeds up the code if we consider in the for loop only odd numbers (for left in range(1, n, 2)) and right%2!=0. for left in range(1, n, 2): right = n-1-left if (right % 2 != 0): ....
Only way to get duplicates is if we pass in the same two permutation of values in the left and right recursive call multiple times in the for loop but that’s impossible here
⭐ MEDIUM Playlist: th-cam.com/video/jzZsG8n2R9A/w-d-xo.html
3:56 'Don't try to be smart just try to figure out how to solve it at all'
Me on every single leetcode problem:
Optimisation: When n is even no full BT is possible.
Actually we can remove all the even numbers from the for loops and input as well. My code got 98% better runtime and 83% better mem. utilization than the rest of the entries.
if n % 2 == 0:
return []
dp = {0 : [], 1 : [TreeNode()]}
def backtrack(n):
if n in dp:
return dp[n]
res = []
for l in range(1,n,2):
r = n - 1 - l
leftTrees,rightTrees = backtrack(l),backtrack(r)
for lt in leftTrees:
for rt in rightTrees:
res.append(TreeNode(0,lt,rt))
dp[n] = res
return dp[n]
return backtrack(n)
One simple observation that will help is if n=even we can't create FBT so we can add a check in first condition if n%2==0 rather than n==0
You did it again! The exact memoization solution I was looking for. You're a monster!
@NeetCode: I guess at 8:20 what you mean to say is to iterate from 1 to n-1. Because the left should have at least 1 left node. Thank you for the solution. Its very easy to follow.
Hey, nice vide.
One thing I notice is that we can start the loop for calculating Left side from 1 , since "l=0" wont be a full binary tree
I think the case where n = 2 is handled in the nested for loop where if either of the leftSubtree and rightSubtree lists is empty, there would be no t1 or t2 to append to the result, therefore it will return an empty result.
@@kevinnguyen1706 hi, I am very confused about why do we need to put the nested loop under the first loop (for l in range(n)), I mean when we go through the first loop, we have the number of nodes on left and right, and after that we use nested loop to build up the tree?
These videos are always helpful and so much better than leetcode submissions by others :)!
If we do not consider n cannot be even, it will lead "time limit exceeded".Better to fix it, should be like below:
def allPossibleFBT(self, n):
# check if n is even, there will be no possible to assemble FBT.
if not n % 2:
return []
dp = {0: [], 1: [TreeNode(0)]}
def backtrack(n):
if n in dp:
return dp[n]
res = []
# As drawing, L should be 1 at least, if L is 0, it won't be an FBT, And the largest L should be (n - 2).
# For avoiding n is even, we need to loop it by 2 numbers.
for l in range(1, n - 1, 2):
r = n - 1 - l
leftTrees, rightTrees = backtrack(l), backtrack(r)
for t1 in leftTrees:
for t2 in rightTrees:
res.append(TreeNode(0, t1, t2))
dp[n] = res
return dp[n]
return backtrack(n)
But how does this guarantee that we can have a FBT？ If we let left go from 0 - n-1, does this mean that a blank left subtree(not a BST) is accepted? First we know that a even number will return None as some friends. In this case I think the range of left should be range(1, n, 2) because we don't want either of the subtree to be empty and we don't want the even ones.
if one of leftTrees or rightTrees is emtpy, then the code in nested loop won't be run.
Amazing Introduction, thk you a lot
leftTrees and rightTrees makes a tree even if each gets an even number of nodes. Now we know we cannot make a complete tree if there are even number of nodes. Not sure how those trees with even number of nodes are getting removed from the answer
I got it! Its in the combination of left and right. If left or right is 0 nothing gets appended.. Thank you for the wonderful videos.
Thank you, I had the same question. That's super important for this problem.
Thank you for the video. When you have sometime please solve 1628. Design an Expression Tree With Evaluate Function
Thanks for uploading! Can you please solve Q44: Wildcard Matching, whenever you have time?
thx for the video
one thing to note:
this is just plain old recursion, there is no real backtracking going on here (i.e we dont manipulate a shared datastructure and then revert the change as we unwind from recursion),
what mechanism is checking that we are actually adding full binary trees into `res`?
Awesome explaination !!!
hi, I am very confused about why do we need to put the nested loop under the first loop (for l in range(n)), I mean when we go through the first loop, we have the number of nodes on left and right, and after that we use nested loop to build up the tree?
Nested inner loop is required to get all the combinations of the possible trees. Take n=7 for an example.
Let's run through the recursion steps. In every step I will take only the ideal choices(I will ignore the choices that will return an empty list, means no reslut), thats how I will be able to explain you the process.
So (1st recursion call), lets assume- left will have (0,1,2,3,4,5,6) right will have (5,4,3,2,1,0) choices
left = 5
right= 1
now right will return immediately with a subtree having left and right child null and root value as 0-->[0,null,null]
(step under consideration) ---->Our recursion will run for left=5.
Again left will have (0,1,2,3,4) right will have (3,2,1,0) choices.
if we take left - 3, right =1and run further through the recursion taking ideal choices(which will be left=1, right=1 in the subsequent setp), the this recusrion call will return return with subtree [0,0,0]
So this call will add [0,0,0,0,0,null,null] to the res array.
Outer for loop for (step under consideration) has not finished yet, there is one more ideal choice,
left =1 (returns with a subtree [0,null.null])
right = 3 (return with a subtree [0,0,0]
So this call will add [0,0,0,null,null,0,0] to the res array.
Now comming back to the (1st recursion call)
left = 5 --> returned( [ [0,0,0,null,null,0,0] , [0,0,0,0,0,null,null] ]
right= 1--> returned [0,null,null]
Inner for loops will run now and generate two unique full binary trees.
[ [0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0] ]
You can use a tree visualizer for better visualization of the trees returned in each step.
eniac00.github.io/btv/
The recursion calls return the possibilities for left and right, but when calculating the overall numbers of possible ways, these left and right possibilities' combinations must be considered as well, that's why
THANKS MR. NEETCODE!!
Is there a way to do this iteratively to get a better time complexity?
No
This is what i need!
Will this code return a solution for even number of nodes? Because we can't make a full binary tree with even number of nodes.
Vey nice remark n needs to be always an odd number so n-1 can be an even, otherwise the result is an empty list (n % 2 == 0), and so if n-1 is even it can be written as the sum of 2 odds integers. And this remark speeds up the code if we consider in the for loop only odd numbers (for left in range(1, n, 2)) and right%2!=0.
for left in range(1, n, 2):
right = n-1-left
if (right % 2 != 0): ....
Loved it
why not use lru chache
Why don't we get any duplicates here?
Only way to get duplicates is if we pass in the same two permutation of values in the left and right recursive call multiple times in the for loop but that’s impossible here
fck this problem !
First
Rust Implemention ->
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option,
// pub right: Option,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::{rc::Rc, cell::RefCell, collections::HashMap};
type T = Option;
macro_rules! treeNode {
($n:expr) => { Some(Rc::new(RefCell::new(TreeNode::new($n)))) };
($a:expr, $b:expr) => { Some(Rc::new(RefCell::new(TreeNode { val: 0, left: $a, right: $b, })))};
}
impl Solution {
pub fn all_possible_fbt(n: i32) -> Vec {
fn bk(n: i32, dp: &mut HashMap) -> Rc {
match n {
0 => dp.get(&0).unwrap().clone(),
1 => dp.get(&1).unwrap().clone(),
_ if dp.contains_key(&n) => dp.get(&n).unwrap().clone(),
_ => {
let mut res = Vec::new();
for l in (1..n).step_by(2) {
let r = n - 1 - l;
for t1 in bk(l, dp).iter() {
for t2 in bk(r, dp).iter() { res.push(treeNode!(t1.clone(), t2.clone())); }
}
}
let res = Rc::new(res);
dp.insert(n, res.clone());
res
}
}
}
let result = bk( n, &mut HashMap::from([ (0, Rc::new(Vec::::new())), (1, Rc::new(vec![treeNode!(0)])), ]));
Rc::try_unwrap(result).unwrap()
}
}
apple