Discussion on Self Balancing Tree Challenge

Sort by

recency

|

182 Discussions

|

4 weeks ago+ 0 comments

Python

class Node:
    def __init__(self, info):
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 
def height(root):
    if root is None:
        return 0
    return max(1+height(root.left),1+height(root.right))
def inOrder(root):
    if root == None:
        return
    inOrder(root.left)
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    inOrder(root.right)
def preOrder(root):
    if root == None:
        return
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    preOrder(root.left)
    preOrder(root.right)
def turnRight(t):
    x=t.left
    y=x.right
    t.left=y
    x.right = t
    return x
def turnLeft(t):
    x=t.right
    y=x.left
    t.right=y
    x.left = t
    return x
def swap(root):
    root.ht = height(root.left) - height(root.right)

    if root.ht > 1:
        if root.left:
            rlt = height(root.left.left) - height(root.left.right)
            if rlt < 0:
                root.left = turnLeft(root.left)
        return turnRight(root)

    if root.ht < -1:
        if root.right:
            rrt = height(root.right.left) - height(root.right.right)
            if rrt > 0:
                root.right = turnRight(root.right)
        return turnLeft(root)

    return root
class BinarySearchTree:
    def __init__(self): 
        self.root = None

#Node is defined as
#self.left (the left child of the node)
#self.right (the right child of the node)
#self.info (the value of the node)

    def insert(self, val):
        #Enter you code here.
        def _insert(root, val):
            if root is None:
                return Node(val)
            if val<root.info:
                root.left = _insert(root.left,val)
            if val>root.info:
                root.right=_insert(root.right,val)
            return swap(root)
        self.root = _insert(self.root,val)
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
k=int(input())
arr.append(k)
for i in range(t+1):
    tree.insert(arr[i])
inOrder(tree.root)
print()
preOrder(tree.root)

5 months ago+ 0 comments

import sys

lines = []

for line in sys.stdin:
    if "Exit" == line.rstrip():
        break
    lines.append(line.split("\n")[0])

nol = lines[0]
treeInput = [int(x) for x in lines[1].split(" ")]
toIns = lines[2]

# print(nol)
# print(treeInput)
# print(toIns)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Initially, new nodes have height 1

class AVLTree:
    def __init__(self):
        self.root = None

    def get_height(self, node):
        return node.height if node else 0
    
    def calculate_height(self, node):
        return 1 + max(self.get_height(node.left), self.get_height(node.right))
        
    def getBalance(self, node):
        return self.get_height(node.left) - self.get_height(node.right)

    # Insertion operation - Add your code here
    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(node.left, data)
        elif data > node.data:
            node.right = self._insert(node.right, data)
        else:
            return
        
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        bf = self.getBalance(node)

        # An assignment / return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        ## LL rotation
        if bf > 1 and data < node.left.data:
            return self.rotate_right(node)
        ## LR rotation
        if bf > 1 and data > node.left.data:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        ## RR rotation
        if bf < -1 and data > node.right.data:
            return self.rotate_left(node)
        ## RL rotation
        if bf < -1 and data < node.right.data:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        # A return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        return node
          
    # A return statement is needed because, when applying a rotation, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
    def rotate_right(self, node):
        left = node.left
        left_right = left.right

        left.right = node
        node.left = left_right

        node.height = self.calculate_height(node)
        left.height = self.calculate_height(left)

        return left
    
    def rotate_left(self, node):
        right = node.right
        right_left = right.left

        right.left = node
        node.right = right_left

        node.height = self.calculate_height(node)
        right.height = self.calculate_height(right)

        return right

    # Traversals
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.inorder(node.right)

    def postorder(self, node):
        if node is not None:
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.postorder(node.left)
            self.postorder(node.right)

    # Function to print BF at each node
    def print_balance(self):
        self.inorder(self.root)
        print("")
        self.postorder(self.root)

tree = AVLTree()
for x in treeInput:
    tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()

11 months ago+ 0 comments

I keep getting this error and I dont know how to reslove PLease help!! avl.java:319: error: cannot find symbol root=root.insert(root,nv); ^ symbol: method insert(Node,int) location: variable root of type Node 1 error class Solution {

 int Max(int a, int b)
{
    if(a>b)
    {
        return a;
    }
    else 
    {
        return b;
    }
}

  Node leftrot(Node x)
{
    Node y = x.right;
    Node t2 = y.left;

    y.left = x;
    x.right = t2;

    x.ht = Max(height(x.left),height(x.right)+1);
    y.ht = Max(height(x.left),height(x.right)+1);

    return y;
}
  Node rightrot(Node x)
{
    Node y = x.left;
    Node t2 = y.right;

    y.right = x;
    x.left = t2;

    x.ht = Max(height(x.left),height(x.right))+1;
    y.ht = Max(height(x.left),height(x.right))+1;

    return y;

}
 int height(Node n)
{
    if(n == null)
    {
        return 0;
    }
    return n.ht;
}
 int getBalance(Node node)
{
    if(node == null)
    {
        return 0;
    }
    return height(node.left) - height(node.right);
}

 Node insert(Node root,int data)
{
    if(root==null)
    {
         Node node = new Node();
        node.val = val;
        node.ht = 0;
        node.left = null;
        node.right = null;
        return node;
    }
    if(root.val < data)
    {
        root.right = insert(root.right, data);
    }
    else if(root.val > data)
    {
        root.left = insert(root.left, data);
    }
    else
    {
        return root;
    }
    root.ht = Max(height(root.left), height(root.right))+1;

    int balance = getBalance(root);

    if(balance > 1 && data < root.left.val)
    {
        return rightrot(root);
    }
    if(balance < -1 && data > root.right.val)
    {
        return leftrot(root);
    }
    if(balance > 1 && data > root.left.val)
    {
        root.left = leftrot(root.left);
        return rightrot(root);
    }
    if(balance < -1 && data < root.right.val)
    {
        root.right = rightrot(root.right);
        return leftrot(root);
    }
    return root;
}

    avl.java:319: error: cannot find symbol
    root=root.insert(root,nv);
             ^

1 year ago+ 0 comments

Js solution

class Node { constructor(value) { this.value = value; this.left = null; this.right = null; this.height = 1; } }

function insert(root, data) { if (!root) return new Node(data);

if (data < root.value) {
    root.left = insert(root.left, data);
} else {
    root.right = insert(root.right, data);
}

root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

const balance = getBalance(root);

if (balance > 1 && data < root.left.value) {
    return rightRotate(root);
}

if (balance < -1 && data > root.right.value) {
    return leftRotate(root);
}

if (balance > 1 && data > root.left.value) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

if (balance < -1 && data < root.right.value) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

return root;

}

function getHeight(node) { return node ? node.height : 0; }

function getBalance(node) { return node ? getHeight(node.left) - getHeight(node.right) : 0; }

function rightRotate(y) { const x = y.left; const T2 = x.right;

x.right = y;
y.left = T2;

y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));

return x;

}

function leftRotate(x) { const y = x.right; const T2 = y.left;

y.left = x;
x.right = T2;

x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));

return y;

}

function sortedArrayToAVL(arr) { if (arr.length === 0) return null;

const mid = Math.floor(arr.length / 2);
const root = new Node(arr[mid]);

root.left = sortedArrayToAVL(arr.slice(0, mid));
root.right = sortedArrayToAVL(arr.slice(mid + 1));

root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

const balance = getBalance(root);

if (balance > 1 && getBalance(root.left) >= 0) {
    return rightRotate(root);
}

if (balance < -1 && getBalance(root.right) <= 0) {
    return leftRotate(root);
}

if (balance > 1 && getBalance(root.left) < 0) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

if (balance < -1 && getBalance(root.right) > 0) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

return root;

}

function inOrderTraversal(node, result = []) { if (!node) return result;

inOrderTraversal(node.left, result);
result.push(``${node.value}(BF=$`{getBalance(node)})`);
inOrderTraversal(node.right, result);

return result;

}

function preOrderTraversal(node, result = []) { if (!node) return result;

result.push(``${node.value}(BF=$`{getBalance(node)})`);
preOrderTraversal(node.left, result);
preOrderTraversal(node.right, result);

return result;

}

function processData(input) { const lines = input.trim().split('\n'); const rootPointer = parseInt(lines[0]); const values = lines[1].split(' ').map(Number); const valueToAdd = parseInt(lines[2]);

let treeAVL;

values.forEach(node => {
    treeAVL = insert(treeAVL, node);
});

treeAVL = insert(treeAVL, valueToAdd);

console.log(inOrderTraversal(treeAVL).join(' '));
console.log(preOrderTraversal(treeAVL).join(' '));

}

processData("4\n3 2 4 5\n6");

2 years ago+ 0 comments

Fully working python solution

import sys

lines = []

for line in sys.stdin:
    if 'Exit' == line.rstrip():
        break
    lines.append(line.split('\n')[0])

nol = lines[0]
treeInput = [int(x) for x in lines[1].split(' ')]
toIns = lines[2]
        
# print(nol)
# print(treeInput)
# print(toIns)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Initially, new nodes have height 1

        
class AVLTree:
    def __init__(self):
        self.root = None

    # Insertion operation - Add your code here
    def insert(self,data):   
        self.root=insertnew(self.root,data)
    # Traversals
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(f"{node.data}(BF={getBalance(node)})", end=" ")
            self.inorder(node.right)
    
    def postorder(self, node):
        if node is not None:
            print(f"{node.data}(BF={getBalance(node)})", end=" ")
            self.postorder(node.left)
            self.postorder(node.right)
            
    # Function to print BF at each node
    def print_balance(self):
        self.inorder(self.root)
        print("")
        self.postorder(self.root)

def insertnew(root,data):
    if root is None:
        return Node(data)
    if root.data<data:
        root.right=insertnew(root.right,data)
    if root.data>data:
        root.left=insertnew(root.left,data)
    root.height=1+max(getheight(root.left),getheight(root.right))
   
# left left case
    if getBalance(root)>1 and data<root.left.data:
        return rotateright(root)
    
    # right right case
    if getBalance(root)<-1 and data>root.right.data: 
        return rotateleft(root)
    
    # left right case
    if getBalance(root)>1 and root.left.data<data:
        root.left=rotateleft(root.left)
        return rotateright(root)
    
    # right left case
    if getBalance(root)<-1 and root.right.data>data:
        root.right=rotateright(root.right)
        return rotateleft(root)
    return root
def getheight(root):
    if root is None:
        return 0
    return root.height
def getBalance(root):
    if root is None:
        return 0
    return (getheight(root.left)-getheight(root.right))

def rotateleft(root):
    y=root.right
    T2=y.left
    # perform rotation
    y.left=root
    root.right=T2
    
    root.height=1+max(getheight(root.left),getheight(root.right))
    y.height=1+max(getheight(y.left),getheight(y.right))
    return y

def rotateright(root):
    y=root.left
    T3=y.right
    # perform rotation
    y.right=root
    root.left=T3
    root.height=1+max(getheight(root.left),getheight(root.right))
    y.height=1+max(getheight(y.left),getheight(y.right))
    return y
tree = AVLTree()

for x in treeInput:
    tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()

Sort by

|

182 Discussions

|

Cookie support is required to access HackerRank