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

#coding #programming #python

QuickBit explaining visually how balancing a binary tree works and how to code it in Python.

[manankoradiya]

This is one the best videos which explains all the points perfectly. It helped me a lot with my assignments. Thank you man.

[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.

[andresausecha]

very useful content, I coded this in Java but used your logic. Like for this video

[codingcompetitiveprogrammi]

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

[rastooooo]

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

[Marco-hdn]

great video but do you really need the background music?

[ozzy-frvj]

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<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::{rc::Rc, cell::RefCell};
type T =
macro_rules! borrow_mut {
($option:expr) => { };
}
macro_rules! borrow {
($option:expr) => { };
}
impl Solution {
pub fn balance_bst(root: T) -> T {
fn T) -> T {
let vine_head =
borrow_mut!(vine_head).right = root;
let mut current = vine_head.clone();
while {
if {
let right =
rotate_right(current.clone(), right);
} else {
current =
}
}
vine_head
}
fn root: T) -> i32 {
let mut count = 0;
while root.is_some() {
count += 1;
root =
}
count
}
fn rotate_right(parent: T, node: T) {
let temp = borrow!(node).left.clone();
borrow_mut!(node).left =
borrow_mut!(temp).right = node;
= temp;
}
fn rotate_left(parent: T, node: T) {
let temp = borrow!(node).right.clone();
borrow_mut!(node).right =
borrow_mut!(temp).left = node;
= 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 =
}
}
//create vine
let vine_head =
// get total node count
let nodecount =
// 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);
}

}
}

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, + 1)))) - 1
rotateLeftByAmount(root, nodecount - countOfPerfectTreeNodes)
while countOfPerfectTreeNodes > 1:
countOfPerfectTreeNodes //= 2
rotateLeftByAmount(root, countOfPerfectTreeNodes)
return root.right