i could not get the rootIndex + mid-left + 1 part, and unfortunately you did not explain it in the video as well, could you please explain how the root of right is starting from here?
@@bahutbadiyakp the formula `rootIndex + (mid - left) + 1` ensures that we correctly identify the starting point of the right subtree in the preorder array, by skipping over the root and the entire left subtree. - `rootIndex`: Current root index in preorder. - `(mid - left)`: Number of elements in the left subtree. - `+ 1`: Skip the root element itself.
Amazing and easy to grasp the concept with your explanation. I got really interested in studying Algo and Data structure with your videos. Really appreciate your way of teaching. Keep up your work
Have seen neetcode video on this problem. array slicing is a expensive operation. There is a good chance the interviewer Might ask to optimise it. Also I found neetcode explanation better. If nikhil did a dry run to explain the start index of right subtree this would have been easier
Being from a non-cs background, I'm struggling with dsa, glad to have discovered your channel. You've made the understanding so simple. Even though I've gone through the core java, I'm unable to come up with an approach to solve such questions, can you please suggest me regarding how to approach such problems.
while there is no definite approach, the best you can do is practice. Start with some of the concepts first. Algorithmic Paradigms: th-cam.com/play/PLFdAYMIVJQHOvoD4gQz7CwEhK3pAXWLdX.html Once you start to understand it, try writing some basic codes. Get started with easy problems: th-cam.com/play/PLFdAYMIVJQHMap2jOyU6-kHjQEL-vxlV2.html This way you will start to build confidence.
Just discovered your channel and subscribed. Great way of teaching! Please try to include Python code as well if it's not much since there aren't many python dsa/leetcode content creators.
i don't understand, if rootIndex is what is used to create the root, then when you do rootIndex + 1 how is it creating the other 'roots' (nodes)? It's easy with the first root because you're just inserting it from the start but i don't get the recursive part. It would have been helpful if you showed at least two iterations instead of just the root ,3, when explaining the code.
everytime the method splitTree is called, it is creating a new root. Which gets assigned to either the left of previous node, or the right of previous node.
Solution with JS class Node { constructor(value){ this.value = value this.left = null this.right = null } } // preorder : value -> left -> right // inorder : left > value -> right // first we need to find the root, that's preorder's first element // we then find the inorder index of the root // then divide the preorder and inorder arrays as left and right child using the inorder index // using recursion build the tree // return the node function buildBinaryTree(preorder, inorder){ if (!preorder.length || !inorder.length) { return null; } let rootValue = preorder[0] let node = new Node(rootValue) let rootIndex = inorder.indexOf(rootValue) let preorderLeft = preorder.slice(1,rootIndex+1) let inorderLeft = inorder.slice(0,rootIndex) node.left = buildBinaryTree(preorderLeft,inorderLeft) let preorderRight = preorder.slice(rootIndex+1) let inorderRight = inorder.slice(rootIndex+1) node.right = buildBinaryTree(preorderRight,inorderRight) return node } const preorder = [3, 9, 20, 15, 7]; const inorder = [9, 3, 15, 20, 7]; console.log(buildBinaryTree(preorder, inorder))
The idea behind this calculation is that in a pre-order traversal, the root of a subtree comes before its left and right children. So, when you move from the root of the current subtree to its right subtree, you need to skip over the nodes of the left subtree in the pre-order traversal. mid - left + 1: This part calculates the number of nodes in the left subtree. mid is the index of the current root node in the in-order traversal, and left is the index of the left boundary of the current subarray. Subtracting left from mid gives you the count of nodes in the left subtree. rootIndex + mid - left + 1: This calculation adds the number of nodes in the left subtree to the index of the current root node. This effectively brings you to the starting index of the right subtree's pre-order traversal. So, this calculation ensures that you start building the right subtree in the pre-order traversal from the correct index, accounting for the nodes already covered by the left subtree. Remember that in a pre-order traversal, the sequence goes: root, left subtree, right subtree.
Hi bro I have a suggestion can you post one vedio about how recursive backtracking works on step by step using code . Becoz I have understood while saw tree but in code I don’t know how it’s first recursive call end and how backtrack took a place and how element store in a particular list pls pls pls I am very exhausted .. I reallly searching for vedios like kind of this step by step but I can’t found anything they are simple dry run code and finishes their lecture . I want you to do this vedio pls
i could not get the rootIndex + mid-left + 1 part, and unfortunately you did not explain it in the video as well, could you please explain how the root of right is starting from here?
The root for the right side can be found by adding the length of the left subtree (mid-left+1) that's why you update it with that
isko bhi nhi pta iss formula ke baare mein... muje toh bahut confusion ho rahi hai.
@@junaidahmad9105 Thank you very much for this comment.
@@bahutbadiyakp the formula `rootIndex + (mid - left) + 1` ensures that we correctly identify the starting point of the right subtree in the preorder array, by skipping over the root and the entire left subtree.
- `rootIndex`: Current root index in preorder.
- `(mid - left)`: Number of elements in the left subtree.
- `+ 1`: Skip the root element itself.
Really like the visualization of the problem and how tree is constructed. Really helped to understand the problem. Thanks
Amazing and easy to grasp the concept with your explanation. I got really interested in studying Algo and Data structure with your videos. Really appreciate your way of teaching. Keep up your work
I think it's insane how you did not even use array slicing like NeetCode does. well done & thanks
Have seen neetcode video on this problem. array slicing is a expensive operation. There is a good chance the interviewer Might ask to optimise it. Also I found neetcode explanation better. If nikhil did a dry run to explain the start index of right subtree this would have been easier
you use the map to get the start index. It will return you in O(1) time...fastest.
lots of love brother. I have been watching your videos for leetcode sokutions. thanks a lot for making such videos !!
So nice of you
Being from a non-cs background, I'm struggling with dsa, glad to have discovered your channel. You've made the understanding so simple.
Even though I've gone through the core java, I'm unable to come up with an approach to solve such questions, can you please suggest me regarding how to approach such problems.
while there is no definite approach, the best you can do is practice. Start with some of the concepts first.
Algorithmic Paradigms: th-cam.com/play/PLFdAYMIVJQHOvoD4gQz7CwEhK3pAXWLdX.html
Once you start to understand it, try writing some basic codes. Get started with easy problems:
th-cam.com/play/PLFdAYMIVJQHMap2jOyU6-kHjQEL-vxlV2.html
This way you will start to build confidence.
Keep up the excellent work. Your explanation technique is brilliant.🤩🤩
Great explanation. Thank you very much
Great explanation
Glad you think so!
Just discovered your channel and subscribed. Great way of teaching! Please try to include Python code as well if it's not much since there aren't many python dsa/leetcode content creators.
thank you for subscribing.. :)
also, I usually focus on understanding the problem and how to solve, rather than the programming language :)
i don't understand, if rootIndex is what is used to create the root, then when you do rootIndex + 1 how is it creating the other 'roots' (nodes)? It's easy with the first root because you're just inserting it from the start but i don't get the recursive part. It would have been helpful if you showed at least two iterations instead of just the root ,3, when explaining the code.
everytime the method splitTree is called, it is creating a new root. Which gets assigned to either the left of previous node, or the right of previous node.
awesome!
Thanks
Solution with JS
class Node {
constructor(value){
this.value = value
this.left = null
this.right = null
}
}
// preorder : value -> left -> right
// inorder : left > value -> right
// first we need to find the root, that's preorder's first element
// we then find the inorder index of the root
// then divide the preorder and inorder arrays as left and right child using the inorder index
// using recursion build the tree
// return the node
function buildBinaryTree(preorder, inorder){
if (!preorder.length || !inorder.length) {
return null;
}
let rootValue = preorder[0]
let node = new Node(rootValue)
let rootIndex = inorder.indexOf(rootValue)
let preorderLeft = preorder.slice(1,rootIndex+1)
let inorderLeft = inorder.slice(0,rootIndex)
node.left = buildBinaryTree(preorderLeft,inorderLeft)
let preorderRight = preorder.slice(rootIndex+1)
let inorderRight = inorder.slice(rootIndex+1)
node.right = buildBinaryTree(preorderRight,inorderRight)
return node
}
const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];
console.log(buildBinaryTree(preorder, inorder))
pls explain why did we write root index as rootindex+mid-left+1 in root->right call
The idea behind this calculation is that in a pre-order traversal, the root of a subtree comes before its left and right children. So, when you move from the root of the current subtree to its right subtree, you need to skip over the nodes of the left subtree in the pre-order traversal.
mid - left + 1: This part calculates the number of nodes in the left subtree. mid is the index of the current root node in the in-order traversal, and left is the index of the left boundary of the current subarray. Subtracting left from mid gives you the count of nodes in the left subtree.
rootIndex + mid - left + 1: This calculation adds the number of nodes in the left subtree to the index of the current root node. This effectively brings you to the starting index of the right subtree's pre-order traversal.
So, this calculation ensures that you start building the right subtree in the pre-order traversal from the correct index, accounting for the nodes already covered by the left subtree.
Remember that in a pre-order traversal, the sequence goes: root, left subtree, right subtree.
@@nikoo28 thanks!!
Hi bro I have a suggestion can you post one vedio about how recursive backtracking works on step by step using code . Becoz I have understood while saw tree but in code I don’t know how it’s first recursive call end and how backtrack took a place and how element store in a particular list pls pls pls I am very exhausted .. I reallly searching for vedios like kind of this step by step but I can’t found anything they are simple dry run code and finishes their lecture . I want you to do this vedio pls
Have you watched my videos on recursion? They cover all the basics.. how it happens step by step
I found the recursive backtracking explanation given by Nikhil to the best in the market. I finally understood it using his technique&explanation
Can be solved with 4 pointers instead of using Map
How?
rushed
what part did you face a problem with?
3rd class