Balancing BSTs: From Theory to Practice with Python and Visual Examples!

[@anon_y_mousse]

This is your best video yet. You illustrated a key point that people forget about binary searches in that you can collapse a tree into an array and vice versa and a sorted array is easily converted back into a binary tree that's perfectly balanced.

[@codingcompetitiveprogrammi6118]

this is best video about algorithm don forget upload more like this thanx for share knowledge

[@bvdlio]

Thank you, I will.

[@themvlek]

That was great video ❤

[@rastooooo]

thanks , i have the same thing with few differences as my task for uni, it helped alot

[@Marco-h5d4n]

great video but do you really need the background music?

[@bvdlio]

Thanks!
Honestly, I don't know. I've asked viewers through polls, but I receive mixed results.
It can quickly distract or be annoying of if its too loud.

[@ozzy-fr7vj]

Constant space, linear time (Most Optimal way to balance bst) Day-Stout-Warren (DSW) algorithm implemenation in rust and python
RUST ->
// 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()
}
}
PYTHON ->
# 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 balanceBST(self, root: TreeNode) -> TreeNode:
def rotateLeft(parent, node):
temp = node.right
node.right = temp.left
temp.left = node
parent.right = temp
def rotateRight(parent, node):
temp = node.left
node.left = temp.right
temp.right = node
parent.right = temp
def rotateLeftByAmount(root, amount):
for _ in range(amount):
rotateLeft(root, root.right)
root = root.right
def createVine(root):
vinehead = TreeNode(0, None, root)
root = vinehead
while root.right:
if root.right.left: rotateRight(root, root.right)
else: root = root.right
return vinehead
def getNodeCount(root):
count = 0;
while root:
count += 1
root = root.right
return count
root = createVine(root)
nodecount = getNodeCount(root.right)
countOfPerfectTreeNodes = int(math.pow(2, math.floor(math.log2(nodecount + 1)))) - 1
rotateLeftByAmount(root, nodecount - countOfPerfectTreeNodes)
while countOfPerfectTreeNodes > 1:
countOfPerfectTreeNodes //= 2
rotateLeftByAmount(root, countOfPerfectTreeNodes)
return root.right