"use strict";
/**
* AVL Tree
*
* @example
* import { AVLTree } from '../../ds/avl-tree';
*
* const avl = new AVLTree();
* avl.insert(10);
* avl.insert(5);
* avl.insert(8);
* avl.insert(4);
* avl.insert(6);
*
* @author Gaurav Soni
*
* @module ds/avl-tree
*
*/
Object.defineProperty(exports, "__esModule", { value: true });
exports.AVLTree = exports.TreeNode = void 0;
/**
* A node inside a AV: tree.
*
* @public
* @constructor
*
* @param {unknown} val - The value stored in the AV: tree
*/
class TreeNode {
constructor(value, left, right, height) {
/**
* Left node
* @member {TreeNode}
*/
this.left = null;
/**
* Right node
* @member {TreeNode}
*/
this.right = null;
/**
* Height of the node
* @member {number}
*/
this.height = 0;
this.value = value;
this.left = left;
this.right = right;
this.height = height;
}
}
exports.TreeNode = TreeNode;
/**
* AVL Tree
*
* @public
* @constructor
*/
class AVLTree {
constructor() {
this.root = null;
}
/**
* Insert the node into the AVL tree at given node. If not provided, root will be consider as current. <br><br>
* Time Complexity: O(logN) in the average case and O(N) in worst case.
*
* @public
* @method
* @param value value that needs to be inserted
* @param current Current Node
* @returns void
*/
insert(value, current = null) {
if (!this.root) {
this.root = new TreeNode(value, null, null, 1);
return;
}
current = current || this.root;
let insertKey;
if (current.value > value) {
insertKey = 'left';
}
else {
insertKey = 'right';
}
if (current && !current[insertKey]) {
current[insertKey] = new TreeNode(value, null, null, 0);
}
else {
this.insert(value, current[insertKey]);
}
}
/**
* Given the root of a binary tree, invert the tree, and return its root.
* <br />
* For example,
* <br />
* <b>Input:</b> [4, 2, 7, 1, 3, 6, 9]
* <br />
* <b>Output:</b> [4, 7, 2, 9, 6, 3, 1]
* <br />
*
* @method
* @see {@link https://leetcode.com/problems/invert-binary-tree/|Invert Binary Tree}
*
* @public
*
* @returns {TreeNode} Inverted AVL tree
*/
invert() {
function invert(root) {
if (!root) {
return null;
}
const left = root.left;
root.left = invert(root.right);
root.right = invert(left);
return root;
}
return invert(this.root);
}
/**
* Given the root of a binary tree, return its maximum depth/height.
* <br /><br />
* A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
* For example,
* <br />
* <b>Input:</b> [3, 9, 20, null, null, 15, 7]
* <br />
* <b>Output:</b> 3
* <br />
*
* @method
* @see {@link https://leetcode.com/problems/maximum-depth-of-binary-tree/|Maximum Depth of Binary Tree}
*
* @public
*
* @returns {Number} Diameter of AVL tree
*/
getHeight() {
function maxDepth(root) {
if (!root) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
return maxDepth(this.root);
}
/**
* Given the root of a binary tree, return the length of the diameter of the tree
* <br /><br />
* The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
* For example,
* <br />
* <b>Input:</b> [1, 2, 3, 4, 5]
* <br />
* <b>Output:</b> 3
* <br />
*
* @method
* @see {@link https://leetcode.com/problems/diameter-of-binary-tree/|Diameter of Binary Tree}
*
* @public
*
* @returns {Number} Height of AVL tree
*/
getDiameter() {
let ans = 0;
function diameterOfBinaryTree(root) {
if (!root) {
return 0;
}
const left = diameterOfBinaryTree(root.left);
const right = diameterOfBinaryTree(root.right);
ans = Math.max(left + right, ans);
return 1 + Math.max(left, right);
}
diameterOfBinaryTree(this.root);
return ans;
}
/**
* Given a binary tree, determine if it is height-balanced.
* <br /><br />
* a height-balanced binary tree is defined as:
* "a binary tree in which the left and right subtrees of every node differ in height by no more than 1."
* For example,
* <br />
* <b>Input:</b> [3, 9, 20, null, null, 15, 7]
* <br />
* <b>Output:</b> true
* <br />
*
* @method
* @see {@link https://leetcode.com/problems/balanced-binary-tree/|Balanced Binary Tree}
*
* @public
*
* @returns {boolean} Tree is balanced or not
*/
isBalanced() {
function checkBalanced(root) {
if (!root) {
return 0;
}
const left = checkBalanced(root.left);
if (left === -1)
return -1;
const right = checkBalanced(root.right);
if (right === -1)
return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
return checkBalanced(this.root) > -1 ? true : false;
}
/**
* Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
* <br /><br />
* A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
* For example,
* <br />
* <b>Input:</b> root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
* <br />
* <b>Output:</b> true
* <br />
*
* @static
* @function
* @see {@link https://leetcode.com/problems/subtree-of-another-tree/|Subtree of Another Tree}
*
* @public
* @param {TreeNode} root root of AVL tree
* @param {TreeNode} subRoot subRoot of AVL tree
*
* @returns {boolean} true if subTree is a tree of another tree otherwise false
*/
static isSubTree(root, subRoot) {
function subTree(_root, _subRoot) {
if (!_root && !_subRoot)
return true;
if (!_root || !_subRoot || _root.value !== _subRoot.value)
return false;
return (subTree(_root.left, _subRoot.left) &&
subTree(_root.right, _subRoot.right));
}
if (!root) {
return false;
}
if (subTree(root, subRoot))
return true;
return (AVLTree.isSubTree(root.left, subRoot) ||
AVLTree.isSubTree(root.right, subRoot));
}
/**
* Given the roots of two binary trees p and q, write a function to check if they are the same or not.
* <br /><br />
* Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
* For example,
* <br />
* <b>Input:</b> p = [1, 2, 3], q = [1, 2, 3]
* <br />
* <b>Output:</b> true
* <br />
*
* @static
* @function
* @see {@link https://leetcode.com/problems/same-tree/|Same Tree}
*
* @public
*
* @param {AVLTree} tree1 First AVL tree
* @param {AVLTree} tree2 Second AVL tree
*
* @returns {boolean} Both trees are same or not
*/
static isSameTree(tree1, tree2) {
function sameTree(root1, root2) {
if (!root1 && !root2)
return true;
if (!root1 || !root2 || root1.value !== root2.value)
return false;
const isLTreeSame = sameTree(root1.left, root2.left);
const isRTreeSame = sameTree(root1.right, root2.right);
return isLTreeSame && isRTreeSame;
}
return sameTree(tree1.root, tree2.root);
}
}
exports.AVLTree = AVLTree;