1382, 108 Balance a Binary Search Tree | Day-Stout-Warren (DSW) Algorithm | In-Place Balancing

[@JeevantSingh-s7g]

The level motivation this guy has is astounding

[@princenagar1686]

This is not astonishing, it's his hard work and consistency. There are actually thousands of people who are doing it right now excluding you. That's why you think it's too much, people actually work real hard and rest just imagine how are they working so hard

[@JeevantSingh-s7g]

I am sorry but do I know you ? Don’t blabber about someone you don’t know. Appreciating something is not equivalent to lacking unlike you of course who cannot even comprehend appreciation. Anyways what’s best for you da

[@mayankjain9821]

Kudos to your hard work in explaining this hard implementation. I had studied AVL earlier in my DSA course so, it was relatively easy to understand this algorithm. But the implementation is so specific that it becomes a subjective implementation.

[@youcanyouwill2004]

Amazing explanation !! Thanks a lot ❤❤❤❤❤❤

[@princenagar1686]

Bro , i have one suggestion for you. The only problem that you have is "Your Over Explaining Things at incorrect moments". This thing just make your simplification real hard. I suggest you to explain what's necessary for that "moment" to understand.

[@harshmaheshwari8631]

exactly

[@princenagar1686]

@@harshmaheshwari8631 yeah it's truth, if he can fix it, he will be next

[@vaxxnsh]

Maksad pura ho gya 👍

[@satwiktatikonda764]

how are you this much consistent bro😱😱

[@princenagar1686]

This is not too much, it's normal if you are actually a serious coder

[@mohammedansil2302]

great video

[@codebreaker6578]

please explain when i am taking vector arr for storing the values in sorted order , and then making tree from the arr is taking 762ms while vector arr is talking 62ms . why the time is differed this much ?

[@btechstudent1620]

just dont care abt the time that leetcode , even u run the same code at a very different time then always u will see huge variation in the time

[@codebreaker6578]

@@btechstudent1620 i know that thing but that's a huge difference and also he mentioned to use TreeNode

[@arnavkaul7827]

That is irrelevant to a certain extent it has something to do with the server as well don't focus on the time taken rather how many edge cases you can pass

[@Munchen888]

Some hints 😊: 1. gather into list 2. use partition to divide on equal parts

[@AmanKumar-cc9ui]

Guys Skewd Case at @1:55 By Mistake Aryan mentioned the TC in worst case would be log(n) it should be O(n).

[@UNKNOWN-zm1jr]

Just amazing bro

[@prathmeshsananse7064]

Amazing work man, keep it coming

[@rhydhamsingla9597]

very nice explanation. I appreciate your efforts brother. I also have an ques, in the video you said that we "assume" that this is gonna give us a perfect tree, so i wanna know that does this algorithm have a fail or that was your way of teaching?

[@6mahine_mein_google]

@18:47 in the example u took in the code it should be parent->left = temp , and this code works in the final code beacuse we are doing left rotations only in the right subtrees of the skewed vinetree .

[@dhaanaanjaay]

You and neetcode both rock🤟🤟🤟

[@theUnkown617]

You said there is no recursive extra space used but in the editorial they mentioned that there will be O(N) extra space for recursive stack could you clarify that ?

[@deepakchalla495]

I saw the problem and the first thought i got was AVL trees but i found it difficult in implementation. This method is easier than that.

[@PulkitAgg13]

Have they asked AVL Tree by using confusing language?

[@shahzodshafizod]

Simpil bro, simpil)

[@aerinpatel8467]

Hard to Move On 👀

[@ozzy-fr7vj]

Rust Soln -> // 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}; type T = Option; macro_rules! borrow_mut { ($option:expr) => { $option.as_ref().unwrap().borrow_mut() }; } macro_rules! borrow { ($option:expr) => { $option.as_ref().unwrap().borrow() }; } impl Solution { pub fn balance_bst(root: T) -> T { fn create_right_skewed_vine_tree(root: T) -> T { let vine_head = Some(Rc::new(RefCell::new(TreeNode::new(0)))); borrow_mut!(vine_head).right = root; let mut current = vine_head.clone(); while borrow!(current).right.is_some() { if borrow!(borrow!(current).right).left.is_some() { let right = borrow!(current).right.clone(); rotate_right(current.clone(), right); } else { current = current.unwrap().borrow().right.clone(); } } vine_head } fn get_right_skewed_vine_tree_node_count(mut root: T) -> i32 { let mut count = 0; while root.is_some() { count += 1; root = root.unwrap().borrow().right.clone(); } count } fn rotate_right(parent: T, node: T) { let temp = borrow!(node).left.clone(); borrow_mut!(node).left = borrow_mut!(temp).right.take(); borrow_mut!(temp).right = node; parent.unwrap().borrow_mut().right = temp; } fn rotate_left(parent: T, node: T) { let temp = borrow!(node).right.clone(); borrow_mut!(node).right = borrow_mut!(temp).left.take(); borrow_mut!(temp).left = node; parent.unwrap().borrow_mut().right = temp; } fn rotation_left_by_amount(mut root: T, count: i32) { for _ in 0..count { let right = borrow!(root).right.clone(); rotate_left(root.clone(), right); root = root.unwrap().borrow().right.clone(); } } //create vine let vine_head = create_right_skewed_vine_tree(root); // get total node count let nodecount = get_right_skewed_vine_tree_node_count(borrow_mut!(vine_head).right.clone()); // get node count of perfect tree let mut perfect_tree_node_count = 2_i32.pow(((nodecount + 1) as f32).log2().floor() as u32) - 1; //shift the extra nodes to the left rotation_left_by_amount(vine_head.clone(), nodecount - perfect_tree_node_count); // make rest of the tree while perfect_tree_node_count > 1 { perfect_tree_node_count /= 2; rotation_left_by_amount(vine_head.clone(), perfect_tree_node_count); } vine_head.unwrap().borrow_mut().right.take() } }