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.
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 < inorder.size && curP < preorder.size 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 }
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.
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) ```
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 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.
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.
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.
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.
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;
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.
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
@@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.
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()
God damn. I was about to give up, but I solved it. I was trying to come up with a brute force solution and the key moments that helped me during my thought process were: 1. Noticing that the first element in preorder is always a root node. 2. Noticing that everything to the left of the root value in inorder list is a left subtree and everything to the right is a right subtree. 3. Then you just need to figure out how to apply a recursion to above 2 statements to build the left and right subtrees.
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.
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?
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:]) ```
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!
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!
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.
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
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.
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 < preorder.length; 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;
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?
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.
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)
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]
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?
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.
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, 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
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!!!
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
For people who struggle to understand why he takes until mid in preorder, even though mid comes from inorder: in preorder array elements that is lefter than root in tree has same count with count of elements lefter than mid element in inorder
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?
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.
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?)?
Preorder and inorder variables make sense only as inputs for the general function. As the number of elements should be the same. Later name preorder and inorder are misleading a bit. Because they do not represent all nodes of the tree and the number of elements in each of them is different. Do I understand this correctly?
Notice there wasnt. Could you explain what the runtime and memory usage is? I was having a hard time trying to factor in the runtime and memory usage of the array slice.
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.
HOW IS THIS A FUN PROBLEM also i think we can use a recursive helper function then construct a hash table in the parent function storing the indices for nodes in the inorder sequence reducing the o(n) operation to o(1) (this is o(n): mid = inorder.index(preorder[0]) )
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 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.
I don't think so. There are three key insights, imo. If you didn't know at least one of them, you'd need to discover all three _and_ realize how they complement each other within 15 minutes each: 1. Discover that a tree's `root` partitions its serial inorder traversal. 2. Discover that a tree's serial preorder traversal's `left_subtree` nodes all precede its `right_subtree` nodes 3. Discover that the length of an inorder traversal's left_partition (i.e. `left_subtree`) can be used to select the `left_subtree`'s nodes from the preorder traversal (because they are the same length, `n_nodes`, and all left_subtree nodes are consecutive in preorder traversal). If you had experience (by working problems) with the first two properties of preorder and inorder traversals, you might be able to connect them and discover the third (which is where we should all be after practicing this problem). However, working through the Blind 75 problems, this is the first time I've worked with inorder traversal- even if I knew what inorder traversal was. I guess perspective is worth 20 IQ points.
// 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);
I'm getting a wrong answer (output = []) when running the code, I've checked several times and it is identical :( Edit: found the issue, was missing a 'not' in front of inorder in the base case!
isn't it inefficient to do recursive calls with slicing? I fell like a better approach would be to have a different recursive function that takes two indices
