🌲Tree Playlist: kzread.info/dash/bejne/gaKH0JSRdbSafbw.html

This is the type of problem you give someone you don't want to hire...

@noelcovarrubias7490

Жыл бұрын

ahahah right? It's doable but very tricky

@ayushpatel5463

9 ай бұрын

It took my 2 days to solve 😂😂

@techlogical8059

5 ай бұрын

Lol 😂

@tzur09

4 ай бұрын

Totaly

@doc9448

2 ай бұрын

@@ayushpatel5463 You're supposed to cheat and learn, not spend 2 days working on pre-solved problems

Easily the hardest 'Medium' I have ever seen. If you didn't get this one, don't be discouraged. Just get really good at recursive thinking and come back to it later.

Thanks for all your help NeetCode and all the effort you put into teaching concepts thoroughly!!

Hi, this is stated MEDIUM but I think it's quite HARD. Anyway, I have an improvement: The lookup of the "pivot" in the Inorder array makes this order of magnitude more complex. The worst case around O(n^2). I took an approach of keeping a stack, whose top tells me if I should close the current subtree. It is O(n). The code as it is is not pleasing to look at, but works: fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? { if (preorder.isEmpty()) return null var curI = 0 val root = TreeNode(preorder[0]) val stack = Stack().apply { this.add(preorder[0]) } var curP = 1 fun hasNext() = curI fun nextInorder() = if (curI >= inorder.size) null else inorder[curI] fun stackPeekOrNull() = if (stack.isEmpty()) null else stack.peek() fun dfs(curNode: TreeNode) { if (hasNext() && nextInorder() != curNode.`val`) { curNode.left = TreeNode(preorder[curP++]) stack.push(curNode.left!!.`val`) dfs(curNode.left!!) } if (nextInorder() == curNode.`val`) { curI++ stack.pop() if (curI >= inorder.size) return } if (nextInorder() == stackPeekOrNull()) { return } if (nextInorder() != curNode.`val` && nextInorder() != stackPeekOrNull()) { curNode.right = TreeNode(preorder[curP++]) stack.push(curNode.right!!.`val`) dfs(curNode.right!!) } } dfs(root) return root }

@sucraloss

10 ай бұрын

Was thinking the same on the difficulty level, this felt like a massive ramp-up compared to the mediums I was doing

@tranpaul4550

6 ай бұрын

agree with you, this one is definitely Hard that requires some tricks and DFS configuration. Thats why I dont trust Leetcode medium and hard labels after a while of grinding.

Looking for the video explanation for LeetCode 106 and found this explanation for 105 is very useful too. Thank you so much! :)

I was also just going through this problem, I really like watching your videos, please keep posting!

@NeetCode

3 жыл бұрын

Thanks, much appreciated 😃

Instead of mid, If we rename it to leftTreeLength then we can understand the partitions very easily

Thank you. This is very easy to understand. You saved me from sitting at the computer for 5 hours more.

I love the structure of your videos! You do such a good job at explaining the approach and how to go about the problem, that I often am able to figure out the code before you even get to that part. Thanks so much!

Yo man this is the easiest explanation I found on the internet you gained a sub

To optimize this further from O(N^2) to O(N): - Create a hashset with the keys being all inorder numbers and their indexes. (Ask your interviewer to confirm all inorder values are UNIQUE). Now instead of having to use inorder.index you can do inorderHash[preorder[0]] Now its still O(N^2) because we are slicing the array every time we do recursion. Lets get rid of that. To handle this we will simply reverse our preorder array, so usually we need to access the first index everytime, now we can just pop the end of the array off everytime instead of slicing to get the correct first index everytime. We basically turned our preorder array into a postorder class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: inorderHash = {}; for i in range(len(inorder)): inorderHash[inorder[i]] = i; preorder.reverse(); return self.build(preorder, inorderHash, 0, len(inorder) - 1); def build(self, postorder, inorderHash, start, end): if start > end: return; postorderNum = postorder.pop(); curIdx = inorderHash[postorderNum]; root = TreeNode(postorderNum); root.left = self.build(postorder, inorderHash, start, curIdx - 1); root.right = self.build(postorder, inorderHash, curIdx + 1, end); return root;

@mprasanth18

Жыл бұрын

Good optimization technique

@illu1na

9 ай бұрын

reverse and pop is great technique. But like spaceoddity1567 said, its really not postorder.

@gustavo-yv1gk

6 ай бұрын

nice

@ZhouHenry

6 ай бұрын

Reversing a preorder array is not equivalent to a postorder array. Other than that, pretty good optimization.

I want to thank you soooo much! The visualizations & level of analysis is exactly what I needed to understand the algorithm-level solution. Your videos are the best!

Storing the index for mid in the hash map would be more efficient IMO. That would lead to time complexity O(n) otherwise it's O(n^2). Adding a section of time complexity is what's missing in most videos. IFF possible, please create time complexity videos for Neet75 and add the pertinent links in the description. That would be super helpful for people who are only using these videos to learn about the right approach to solving these problems. ``` # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # takes the left and right bound of inorder, logic --> any given inorder index bisects the tree in left and right subtree def localBuildTree(leftBound, rightBound): nonlocal preOrderListIndex if leftBound > rightBound: return None newRootVal = preorder[preOrderListIndex] newRoot = TreeNode(newRootVal) preOrderListIndex += 1 newRoot.left = localBuildTree(leftBound, inorderIndexFor[newRootVal]-1) newRoot.right = localBuildTree(inorderIndexFor[newRootVal]+1, rightBound) return newRoot inorderIndexFor = dict() for index,element in enumerate(inorder): inorderIndexFor[element] = index preOrderListIndex = 0 return localBuildTree(0, len(preorder)-1) ```

@hypnotic9595

6 ай бұрын

Yes, I like your implementation much better. Using the splice operator, as in his example, will also cost O(n) each time it occurs I think.

the very best explanation for this problem. thank you!!

Great explanation, my friend. Keep up the good work!

How are you using mid from the inorder subarray to slice the preorder?

@galshufi

Жыл бұрын

Notice that mid is equal to the number of nodes on the left tree

Great Explanation, was elated to have found such good help.

But the time and space complexity are both O(n^2) because of the inorder.index() function and passing subarrays of preorder/inorder in each stack of the recursion.

@gouthamr8214

2 жыл бұрын

We can create a hash map and make it a constant time operation

@shriharikulkarni3986

2 жыл бұрын

@@gouthamr8214 We are passing the sublist at each call, creating hashmap requires O(n) time only right?

@gouthamr8214

2 жыл бұрын

@@shriharikulkarni3986 creating hashmap will be O(n) but accessing will be a constant time operation

@shriharikulkarni3986

2 жыл бұрын

@@gouthamr8214 at each step why should we create hashmap if i am only traversing once ? After i travel once that too i return at the first hit itself, i never use that same hashmap again in the code ever.

@gouthamr8214

2 жыл бұрын

@@shriharikulkarni3986 u just have to create hashmap once

The solution is very clear and precise thanks.

Very nice explanation! Thank you!

A few things to improve speed or in general: 1) As several people have mentioned, using the index function is inefficient and will search through inorder in linear time until the corresponding value is found. It would be better to build a dictionary and continue to use that (e.g. with a helper function). Alternatively, at least in Java, using an array (list in python) as a map due to the limited input domain is more efficient. 2) Splicing is pretty inefficient as it takes extra time and memory to create the lists. It would be better to create a helper function and use indices.

@abdullahshahid9051

Жыл бұрын

Building the dictionary takes linear time too. Also note that index function does less work every recursive call due to the divide and conquer nature of this problem

@bob_jones

Жыл бұрын

@@abdullahshahid9051 That is true. However, as you mentioned, the work happens every recursive call. In the best and average case time complexities, the in-order search will be O(n lg(n)), considering all the recursive calls, and worst case O(n^2). If you modify the method to only have the dictionary built once, then it will be O(n) for best, average, and worst cases, considering all the recursive calls.

@abdullahshahid9051

Жыл бұрын

@@bob_jones That's a good point, I didn't think of it that way

@StfuSiriusly

Жыл бұрын

if you use a deque you can get O(n) from collections import deque class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def helper(bound=None): if not inorder or inorder[0] == bound: return None root = TreeNode(preorder.popleft()) root.left = helper(root.val) inorder.popleft() root.right = helper(bound) return root inorder = deque(inorder) preorder = deque(preorder) return helper()

4:45. The 2nd value in preorder is not guaranteed to be the left node because it might not have a left node. What is guaranteed is in preorder = [root, [leftSubTreeValues], [rightSubTreeValues]]. A node's left subtree values come before its right subtree values in preorder traversal if looking at it in array form.

@connorwelch6265

2 жыл бұрын

I also noticed this when he said that. In the example tree, if we take out the 9, the root of 3 has just a right sub tree. What we do know is that any value to the right of a node in preorder is a child. We just do not know which one.

@ThePacemaker45

11 ай бұрын

that wasn't relevant to his solution so I guess he just misspoke there. Good catch though I wondered the same thing.

@sameerkrbhardwaj7439

9 ай бұрын

if we don't have 9 then in preorder list after one recursion the list will be empty and hence we will get null value for left subtree

LOVE IT! I thought it would be a hard one but you make it so easy!!! I figure out the code just from your drawing explanation, because you explain the concept so clearly!!!

Woah! A really clear elaboration I have ever heard

Thanks for the explanation, it was really helpful. You are the Mr.Miyagi of Competitive Coding. P.S: Please keep posting !

@meowmaple

2 жыл бұрын

leetcode*, not competitive programming

This is a really good explanation. Perhaps the best one I’ve seen. Also, an unpopular opinion: it is quite a good problem too as in it ties both of the in-order and pre-order traversal techniques.

simple, clear and short!

wow, such a neat solution. following the same thoughts, I was able to crack LC106

you just made a complicated problem seem f**n easy. Thank you!!

Thank you NeetCode so much

thank you so much. Just used this for my final exam!!

Thanks for the explanation, helps a lot!

@NeetCode

2 жыл бұрын

Glad it helped!

Best solution explanation for this problem on internet :D

Really nice explanation. Thanks 👍

I don't think it's explicitly stated here (apologies if it is), but not only is the root the first element of the preorder, but all the left subtree items come before the right subtree which is way taking the first mid items only gets left subtree values. And buildtree recursing in preorder (root, left, right) is necessary. This is my mod to use a hashmap and indexing to get linear time. class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: inorder_idx_by_val = {inorder[i]:i for i in range(len(inorder))} def _buildTree(pi, pj, ii, ij): if (pi > pj) or (ii > ij): return None node = TreeNode(val=preorder[pi]) mid = inorder_idx_by_val[node.val] node.left = _buildTree(pi+1, pi+(mid-ii), ii, mid-1) node.right = _buildTree(pi+(mid-ii)+1, pj, mid+1, ij) return node return _buildTree(0, len(preorder)-1, 0, len(inorder)-1) Your channel is awesome and thanks for putting all this out there.

@ajvercueil8111

3 ай бұрын

this is the best code i've seen for this problem, way to go!

thanks for making it simple

Elegance logic and code implementation. You always surprises me. 💥

Great explanation thank you so much.

There's no way for me to think of this solution. Good explanation, thanks!

The moment i start the video i like it coz i already know the explanation is gonna be awesome

love the solution as always 😩

One issue with this approach (on an edge case): if the tree is nearly vertical (width 1 each level, randomly left or right), then .index would take O(n) time on average and O(n^2) total. This can be avoided in an iterative method w/ hashmap.

Finding the index is O(N) I would allocate a map pointing all the in order values to its index so you can look up indexes in O(1), but at the cost of some space complexity

@mearaftadewos8508

2 жыл бұрын

nice point: io = {} j = 0 for i in inorder: io[i] = j j += 1 root = Node(preorder[0]) mid = io[preorder[0]]

@JohnnyMetz

2 жыл бұрын

But creating the mapping takes O(n), which is the same as .index(), so I don't think this will help.

@airsoftbeast11234

2 жыл бұрын

@@JohnnyMetz it definitely helps, it’s O(n) preprocessed one time, this is O(N) within every recursive loop

Really helpful video. The explanation was very thorough and helpful

Awesome explanation thank you

Since the first value in preorder is always the root, isn't it also possible to use preorder[1:] as inputs for both left and right instead of using mid to split it?

@khalilkhawaja4909

6 ай бұрын

No, because if there is no left node to the root, then mid would be 0.

Excellent vid

LETS GO! This is the first time I completed a problem by myself where it looks identical to yours, that felt good

@brawlboy1382

8 ай бұрын

There is NO WAY you solved it unless it took you like days

@Lukeisun7

8 ай бұрын

@@brawlboy1382 I think it took like an hour and a lot of pen and paper work haha

Neatest coding channel out there 😎

Thanks @NeetCode for everything you are doing. I know your solution is awesome. But, I just tried your subsequent solution (build binary tree from in-order and post-order) and try to implement this problem and it looks like it is working as expected and efficient too def buildTree_nc(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]: map_inorder = { v : i for i,v in enumerate(inorder)} def helper(l, r): if l > r: return None root = TreeNode(preorder.pop(0)) idx = map_inorder[root.val] if idx - l > 0: root.left = helper(l, idx - 1) if r - idx > 0: root.right = helper(idx + 1, r) return root return helper(0, len (preorder)-1)

Thank You!

does the subarray in python add space complexity? As opposed to using start and end pointers?

loves from India and thank you sir

Damn, this Python's slicing is very very powerful. This makes superior to the other programming langauge when it comes to coding interview.

@sathyapraneethchamala9147

Жыл бұрын

true!! struggling with AddressSanitizer: heap-buffer-overflow in c++ from past few hours!!

You should also consider the Time complexity of this solution which is nlogn. Easy to use a map of value:index for inorder to get index position in constant time making the overall time complexity n.

well explained!!

Greattt videos man. Can you do time and space at end of each video. That would literally finish whole cycle.

The solution is concise enough. But time and space complexity may be way better. Instead of creating new lists for each subproblem we can use pointers which will represents boundaries (left, right) in main preorder. And also instead of iterating in each subproblem through inorder to get current number index we can create map, which will store indices of each number. We will have space O(n) & time O(n) On leetcode solution with these improvements runs at least 3 times faster.

Love you 3000! @NeetCode

Great Explanation.. Thank you..!!

@anikethpaul3657

2 жыл бұрын

did the solution worked on leetcode?

@24_anjalikeshri57

2 жыл бұрын

@@anikethpaul3657 yes..

@anikethpaul3657

2 жыл бұрын

@@24_anjalikeshri57 not working for me tho. Can you share your leetcode profile? I want to see your solution if possible.

@24_anjalikeshri57

2 жыл бұрын

@@anikethpaul3657 class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: return None root=TreeNode(preorder[0]) mid=inorder.index(preorder[0]) root.left=self.buildTree(preorder[1:mid+1],inorder[:mid]) root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:]) return root

Thanks!

Please make a video on binary tree construction from preorder and postorder traversals!

You mentioned that with preorder traversal, the value to the right of another is always the left subtree root. This is not true. In the example tree, if you take away the 9 the root node of 3 has just a right subtree. What we do know with preorder is that any node to the right of another is a child node. We just don't know which one. The solution still works because when we partition the tree we would get an empy list on the left recursive call and return nullptr as our inorder traversal would have the root at the far left of the list and indicating no left children. Just want to clarify this.

@richardnorth1881

Жыл бұрын

Yes, agreed. I pretty much came down to the comments because I was thinking the exact same thing.

I was just going through this problem. 😃

Good explanation! I couldn't come up with the idea to partition the pre-order array. Is the reason why you're partitioning the pre-order array with the left and right sub-array sizes of the in-order array because in pre-order left sub-tree comes before right sub-tree?

@NeetCode

3 жыл бұрын

Yes thats exactly correct.

@vivekshaw2095

2 жыл бұрын

you dont need to partition it you could just pop(0) the value and then pass preorder in both recursion

The code can't be more efficient❤❤

Thanks, G.O.A.T . all time savior

Amazing tyty, and I love your channel name lmao

My solution beats 98.95% in runtime and 91.32% in memory. It uses stack, use preorder to go down (add left/right node) and inorder to go up: let result = new TreeNode(preorder[0]); let stack = [result]; let current = result; let j = 0; // inorder pointer let addSide = 0; // 0 left, 1 right for (let i = 1; i console.log('ADD LEFT', current.val); console.log('stack[stack.length - 1]', stack[stack.length - 1].val); // going up the tree; while (inorder[j] === stack[stack.length - 1].val) { current = stack.pop(); j++; addSide = 1; // if going up then the next add side is right if (stack[stack.length - 1] === undefined) break; } // going down the tree after adding if (addSide === 0) { current.left = new TreeNode(preorder[i]); current = current.left; } else { current.right = new TreeNode(preorder[i]); current = current.right; } stack.push(current); addSide = 0; } return result;

for the preorder indexing, I prefer to say left_size = mid and then use left_size instead of mid. It makes more sense for my mind - since I feel like mid was used more in the context of inorder (as an index of inorder) rather than preorder. For the inorder indexing, I use mid though, cause it makes sense not to include the midpoint. Ex. ``` root = TreeNode(preorder[0]) mid = inorder.index(root.val) left_size = mid root.left = self.buildTree(preorder[1:1+left_size], inorder[:mid]) root.right = self.buildTree(preorder[1+left_size:], inorder[mid+1:]) ```

@donggyunnam8930

2 ай бұрын

I was not able to understand indexing of preorder part but this comments got me. Thank you!

This should be labelled hard🤯

Amazing

mid is found from inorder but why can you use it to index elements in preorder? Will the lengths of inorder and preorder be identical throughout the recursions and array splitting?

@OMFGallusernamesgone

2 жыл бұрын

im sure his version works, but i just followed his logic from his explanation, slice preorder by the lengths of the inorder subarrays

Thank you very much for the videos. They helped me a lot! I wrote down the code for Inorder and Postorder Traversal, based on this video 😀 if len(inorder)==0 or len(postorder)==0: return None tree_len = len(postorder) root = TreeNode(postorder[tree_len -1]) mid = inorder.index(postorder[tree_len -1]) root.left = self.buildTree(inorder[:mid], postorder[0:mid]) root.right = self.buildTree(inorder[mid+1:], postorder[mid:tree_len -1]) return root

thx~!!!!!!

I code in Java...but I watch your videos for better explanation...and code it myself...how cool

you are awesome

I got asked this question in my bloomberg interview, and i blew it!

awesome

Finding the algorithm is not that hard for this (or at least the pattern). It's writing code for this that is hard. Thanks man!

Python Code | much more efficient solution in time and space | Improvised from neetcode solution | Must read Improvements: 1. Create a hashmap to retrieve index 2. Pass current interval of preorder and inorder instead of slicing class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def r_build_tree(preorder_left, preorder_right, inorder_left): if preorder_left == preorder_right: return None nonlocal inorder_hash_map inorder_root_index = inorder_hash_map[preorder[preorder_left]] - inorder_left root = TreeNode(preorder[preorder_left]) root.left = r_build_tree(preorder_left + 1, preorder_left + inorder_root_index + 1, inorder_left) root.right = r_build_tree(preorder_left + inorder_root_index + 1, preorder_right, inorder_left + inorder_root_index + 1) return root inorder_hash_map = {} for index, node in enumerate(inorder): inorder_hash_map[node] = index return r_build_tree(0, len(preorder), 0)

@bishalhazarika135

Жыл бұрын

Your code is longer . How it is effiicient wow. It seem more complex

@illu1na

9 ай бұрын

Thanks its great. personally, it makes more sense for me to use L, R pointers for inorder rather than preorder as per Neetcode's suggestion. Here is mine, i don't like nonlocal stuffs so i made it into separate function. class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: self.index_map = { val: i for i, val in enumerate(inorder) } return self.build_tree_recur(preorder, inorder, 0, 0, len(inorder) - 1) def build_tree_recur(self, preorder, inorder, preorder_start, inorder_start, inorder_end): if preorder_start >= len(preorder) or inorder_start > inorder_end: return None root = TreeNode(val=preorder[preorder_start]) mid = self.index_map[root.val] root.left = self.build_tree_recur(preorder, inorder, preorder_start + 1, inorder_start, mid - 1) root.right = self.build_tree_recur(preorder, inorder, preorder_start + mid - inorder_start + 1, mid + 1, inorder_end) return root

if not preorder or not inorder: return None # Take the root values of subtrees from queue root_val = preorder.pop(0) root = TreeNode(root_val) # Find that root val's index in inorder list to compute the LEFT and RIGHT ind = inorder.index(root_val) root.left = self.buildTree(preorder, inorder[:ind]) root.right = self.buildTree(preorder, inorder[ind+1:]) return root

I don't really get why we pass `preorder[1:mid+1]` for building the left sub tree🤔

@eddiej204

Жыл бұрын

Ah, I see. Because `mid` from inorder array tells us how many items which will be in the left sub tree. So we count from that. preorder = [400,9,1,2,20,15,17] inorder = [1,9,2,400,15,20,7] mid = 3 (3 is an index when the number is 400) left sub tree will contain [1,9,2] right sub tree will contain [15,20,7] preorder[1:mid+1] = [9,1,2]

If the interviewer gives you this question, he doesn't want you.

Thanks for explanation! Still the confusing part for me is that you're using the same "mid" index for both preorder and inorder arrays and cannot catch an idea why is it working :)

@leah7291

Жыл бұрын

That's explained around 12:05 "mid" is the index in the inorder array and also the length of the left subtree after 1 in the preorder array

@calculatorcalculator5998

Жыл бұрын

@@leah7291, yeah, but the neurons in my brain stubbornly resisted making the necessary connections. Now I finally seem to understand. But it's not something I could ever have figured out on my own

This one made me cry from feeling dumb

I really liked this solution, but I have one question regarding dividing our preorder list, how did you arrive at the solution of choosing the left half and right half based on a pt you found in inorder list? Did my question made any sense?

@chenpr

Жыл бұрын

Since mid is equal to the number of nodes on the left subtree. So we use mid to slice preorder arr because we know that the following 'mid' numbers of nodes after the root should be in left subtree.

@victoriatfarrell

9 ай бұрын

Thanks@@chenpr , that was very helpful

I got a variation of this in a real interview where the interviewer swapped the LR order in preorder array. I could get the code working in JS but was hired. Now I'm the CEO of the company.

nice solution, but you probably want to create a dictionary for looking up the root index in the inorder list-otherwise you're doing an O(n) look for each mid, which is O(log n) for the average case but O(n^2) in the worst case.

I get it how the inorder list can be split with the mid index, but the preorder one is still a bit magic for me.

I had a "omg" moment at 7:05

What is the time/space complexity of this solution?

@14:49 why should we include the mid index? the left part only include 1 index to mid-1 index right?..the mid is the root node itself

Great solution vids. Just a heads up in the base case here, you do not have to check "preorder or inorder". They should progress with the exact same amount in each array so you just check if one of them is empty.

It's actually a deceptively tough question.

// For java lovers // We basically need to find the things we see in the example picture from the two arrays given we know the value of mid. int[] leftPreorder = Arrays.copyOfRange(preorder, 1, mid + 1); // second parameter is exclusive just like python. int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid); int[] rightPreorder = Arrays.copyOfRange(preorder, mid + 1, preorder.length); int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length); root.left = helper(leftPreorder, leftInorder); root.right = helper(rightPreorder, rightInorder);

Your solution has ~90MB memory usage, while this one have only 19MB memory usage (because we do not copy inorder/preorder sublists). class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: inorder_value_to_index = {value: x for x, value in enumerate(inorder) } node_index = 0 def build(left, right): nonlocal node_index if left > right: return None node = TreeNode(preorder[node_index]) split_point = inorder_value_to_index[node.val] node_index += 1 node.left = build(left, split_point - 1) node.right = build(split_point + 1, right) return node return build(0, len(preorder) - 1)

through this explanation, it made more sense but this is definitely not a medium level question.

Only thing that is missing from Neetcode's otherwise almost perfect video is the time and space complexity analysis. So is his solution O(n^2) for time (n recur * n item slicing) and also O(n^2) space (n recur * each recur requiring n space?)?