Code is in Java In pictures I will provide full code, AVL Tree utilizes BinNode Class that will provide here and in image The AVL tree is an extension of a BinaryTree and uses its search method... but for some reason search method cannot find the data even though it should be in the tree (For AVL it does not work but for Binary Tree it does)... can you please provide help in fixing the SearchMethod to work with AVL Tree? //Binary Tree Search Method public BinNode search(String val) { return search(this.getRoot(), val); } private BinNode search(BinNode r, String val) { if (r == null) { return null; } int comparison = val.compareTo(r.getData()); if (comparison < 0) { return search(r.getLeft(), val); } else if (comparison > 0) { return search(r.getRight(), val); } else { return r; } } //Bin Node Class public class BinNode { private String data; private BinNode left; private BinNode right; private int height; private boolean color; private BinNode parent; public BinNode(){ data = ""; left = null; right = null; parent = null; color = false; // Default color is black } public boolean getColor() { return color; } public void setColor(boolean color) { this.color = color; } public BinNode getParent() { return parent; } public void setParent(BinNode parent) { this.parent = parent; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } public BinNode(String d){ data = d; left = null; right = null; } public void setData(String d){ this.data = d; } public String getData(){ return this.data; } public void setLeft(BinNode l){ this.left = l; } public BinNode getLeft(){ return this.left; } public void setRight(BinNode r){ this.right = r; } public BinNode getRight(){ return this.right; } }   //AVL Tree Class public class AVLTree extends BinaryTree { private BinNode root; AVLTree() { root = null; } private int height(BinNode node) { return (node == null) ? 0 : node.getHeight(); } private int getBalance(BinNode node) { return (node == null) ? 0 : height(node.getLeft()) - height(node.getRight()); } private BinNode rightRotate(BinNode y) { BinNode x = y.getLeft(); BinNode T2 = x.getRight(); x.setRight(y); y.setLeft(T2); y.setHeight(Math.max(height(y.getLeft()), height(y.getRight())) + 1); x.setHeight(Math.max(height(x.getLeft()), height(x.getRight())) + 1); return x; } private BinNode leftRotate(BinNode x) { BinNode y = x.getRight(); BinNode T2 = y.getLeft(); y.setLeft(x); x.setRight(T2); x.setHeight(Math.max(height(x.getLeft()), height(x.getRight())) + 1); y.setHeight(Math.max(height(y.getLeft()), height(y.getRight())) + 1); return y; } @Override public void insert(String data) { root = insert(root, data); } private BinNode insert(BinNode node, String data) { if (node == null) { return new BinNode(data); } int cmp = data.compareTo(node.getData()); if (cmp < 0) { node.setLeft(insert(node.getLeft(), data)); } else if (cmp > 0) { node.setRight(insert(node.getRight(), data)); } else { // Duplicate values are not allowed in this AVL tree return node; } node.setHeight(1 + Math.max(height(node.getLeft()), height(node.getRight()))); int balance = getBalance(node); if (balance > 1) { if (data.compareTo(node.getLeft().getData()) < 0) { return rightRotate(node); } else { node.setLeft(leftRotate(node.getLeft())); return rightRotate(node); } } if (balance < -1) { if (data.compareTo(node.getRight().getData()) > 0) { return leftRotate(node); } else { node.setRight(rightRotate(node.getRight())); return leftRotate(node); } } return node; } @Override public void remove(String data) { root = remove(root, data); } private BinNode remove(BinNode node, String data) { if (node == null) { return node; } int cmp = data.compareTo(node.getData()); if (cmp < 0) { node.setLeft(remove(node.getLeft(), data)); } else if (cmp > 0) { node.setRight(remove(node.getRight(), data)); } else { // Node found, perform deletion if (node.getLeft() == null || node.getRight() == null) { BinNode temp = (node.getLeft() != null) ? node.getLeft() : node.getRight(); if (temp == null) { temp = node; node = null; } else { node = temp; } } else { BinNode temp = minValueNode(node.getRight()); node.setData(temp.getData()); node.setRight(remove(node.getRight(), temp.getData())); } } if (node == null) { return node; } node.setHeight(1 + Math.max(height(node.getLeft()), height(node.getRight())));

Code is in Java

In pictures I will provide full code, AVL Tree utilizes BinNode Class that will provide here and in image

The AVL tree is an extension of a BinaryTree and uses its search method... but for some reason search method cannot find the data even though it should be in the tree (For AVL it does not work but for Binary Tree it does)... can you please provide help in fixing the SearchMethod to work with AVL Tree?

//Binary Tree Search Method

public BinNode search(String val)
{
return search(this.getRoot(), val);
}
private BinNode search(BinNode r, String val)
{

if (r == null) {
return null;
}

int comparison = val.compareTo(r.getData());

if (comparison < 0) {
return search(r.getLeft(), val);
} else if (comparison > 0) {
return search(r.getRight(), val);
} else {
return r;
}
}

//Bin Node Class

public class BinNode
{
private String data;
private BinNode left;
private BinNode right;

private int height;

private boolean color;

private BinNode parent;


public BinNode(){
data = "";
left = null;
right = null;
parent = null;
color = false; // Default color is black
}

public boolean getColor() {
return color;
}

public void setColor(boolean color) {
this.color = color;
}
public BinNode getParent() {
return parent;
}

public void setParent(BinNode parent) {
this.parent = parent;
}

public int getHeight() {
return height;
}

public void setHeight(int height) {
this.height = height;
}
public BinNode(String d){
data = d;
left = null;
right = null;
}

public void setData(String d){
this.data = d;
}
public String getData(){
return this.data;
}
public void setLeft(BinNode l){
this.left = l;
}
public BinNode getLeft(){
return this.left;
}
public void setRight(BinNode r){
this.right = r;
}
public BinNode getRight(){
return this.right;
}
}

//AVL Tree Class

public class AVLTree extends BinaryTree {

private BinNode root;

AVLTree() {
root = null;
}

private int height(BinNode node) {
return (node == null) ? 0 : node.getHeight();
}

private int getBalance(BinNode node) {
return (node == null) ? 0 : height(node.getLeft()) - height(node.getRight());
}

private BinNode rightRotate(BinNode y) {
BinNode x = y.getLeft();
BinNode T2 = x.getRight();

x.setRight(y);
y.setLeft(T2);

y.setHeight(Math.max(height(y.getLeft()), height(y.getRight())) + 1);
x.setHeight(Math.max(height(x.getLeft()), height(x.getRight())) + 1);

return x;
}

private BinNode leftRotate(BinNode x) {
BinNode y = x.getRight();
BinNode T2 = y.getLeft();

y.setLeft(x);
x.setRight(T2);

x.setHeight(Math.max(height(x.getLeft()), height(x.getRight())) + 1);
y.setHeight(Math.max(height(y.getLeft()), height(y.getRight())) + 1);

return y;
}

@Override
public void insert(String data) {
root = insert(root, data);
}

private BinNode insert(BinNode node, String data) {
if (node == null) {
return new BinNode(data);
}

int cmp = data.compareTo(node.getData());

if (cmp < 0) {
node.setLeft(insert(node.getLeft(), data));
} else if (cmp > 0) {
node.setRight(insert(node.getRight(), data));
} else {
// Duplicate values are not allowed in this AVL tree
return node;
}

node.setHeight(1 + Math.max(height(node.getLeft()), height(node.getRight())));

int balance = getBalance(node);

if (balance > 1) {
if (data.compareTo(node.getLeft().getData()) < 0) {
return rightRotate(node);
} else {
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
}

if (balance < -1) {
if (data.compareTo(node.getRight().getData()) > 0) {
return leftRotate(node);
} else {
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
}

return node;
}

@Override
public void remove(String data) {
root = remove(root, data);
}

private BinNode remove(BinNode node, String data) {
if (node == null) {
return node;
}

int cmp = data.compareTo(node.getData());

if (cmp < 0) {
node.setLeft(remove(node.getLeft(), data));
} else if (cmp > 0) {
node.setRight(remove(node.getRight(), data));
} else {
// Node found, perform deletion
if (node.getLeft() == null || node.getRight() == null) {
BinNode temp = (node.getLeft() != null) ? node.getLeft() : node.getRight();

if (temp == null) {
temp = node;
node = null;
} else {
node = temp;
}
} else {
BinNode temp = minValueNode(node.getRight());
node.setData(temp.getData());
node.setRight(remove(node.getRight(), temp.getData()));
}
}

if (node == null) {
return node;
}

node.setHeight(1 + Math.max(height(node.getLeft()), height(node.getRight())));

int balance = getBalance(node);

if (balance > 1) {
if (getBalance(node.getLeft()) >= 0) {
return rightRotate(node);
} else {
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
}

if (balance < -1) {
if (getBalance(node.getRight()) <= 0) {
return leftRotate(node);
} else {
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
}

return node;
}

private BinNode minValueNode(BinNode node) {
BinNode current = node;
while (current.getLeft() != null) {
current = current.getLeft();
}
return current;
}

public void display() {
display(root);
}

private void display(BinNode node) {
if (node != null) {
display(node.getLeft());
System.out.print(node.getData() + " ");
display(node.getRight());
}
}
}