Discussion on Self Balancing Tree Challenge

Sort by

recency

|

180 Discussions

|

3 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);
             ^

7 months 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");

10 months 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()

11 months ago+ 1 comment

Python template

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):    
    
    # 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()

1 year ago+ 0 comments

My Java Solution with code explanation: https://github.com/tuphan22028238/DSA/blob/main/BT10/06_AVLTree/Solution.java

Sort by

|

180 Discussions

|

Cookie support is required to access HackerRank