Are AVL trees equal? - revision 3

The original question


Given two binary trees, return true if they are structurally
identical, and false otherwise.

Are AVL trees equal?

Are AVL trees equal? - revision 2

This revision on GitHub

In this revision:

• equals() is documented. Two trees are equal if they are structurally identical.

• AvlTree has a type parameter T extends Comparable.

• Sizes of compared trees are used as a quick rejection. But I tested insertion of 10M items to two trees. There is no performance benefit in using size. The result is shown below.

AvlTree.

```
package com.bst;

import java.util.LinkedList;
import java.util.Queue;

public class AvlTree> {

Node root;
private int size;

public AvlTree() {
}

public AvlTree(T... keys) {
insert(keys);
}

private Node insert(Node parent, T key) {
if (parent == null) {
size++;
return new Node(key);
}
if (key.compareTo(parent.key) 0) {
parent.right = insert(parent.right, key);
}
return balance(parent);
}

public int getSize() {
return size;
}

private Node balance(Node p) {
fixHeight(p);
if (bfactor(p) == 2) {
if (bfactor(p.right) 0) {
p.left = rotateLeft(p.left);
}
return rotateRight(p);
}
return p;
}

private Node rotateRight(Node p) {
Node q = p.left;
p.left = q.right;
q.right = p;
fixHeight(p);
fixHeight(q);
return q;
}

private Node rotateLeft(Node q) {
Node p = q.right;
q.right = p.left;
p.left = q;
fixHeight(q);
fixHeight(p);
return p;
}

private int height(Node p) {
return p == null ? 0 : p.height;
}

private int bfactor(Node p) {
return height(p.right) - height(p.left);
}

private void fixHeight(Node p) {
int hl = height(p.left);
int

p.height = (hl > hr ? hl : hr) + 1;

For this sort of stuff you should use Math.max. It reads better. The JVM will handle inlining if it is needed.

I can't really find any other in-code improvements.

StackExchange Code Review Q#107150, answer score: 2