class TreeNode {
    data: number
    left: TreeNode | null = null
    right: TreeNode | null = null
    
    constructor(n: number) {
        this.data = n
    }
}

class BinarySearchTree {
    root: TreeNode | null = null

    insert(root: TreeNode | null, data: number): void {
        if (root === null) {
            const newNode = new TreeNode(data);
            if (this.root === null) {
                this.root = newNode;
            } else {
                root = newNode;
            }
            return;
        }

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

    getHeight(root: TreeNode | null): number {
        if (root === null) {
            return 0;
        }

        const leftHeight = this.getHeight(root.left);
        const rightHeight = this.getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }      

}