ds/binary-search-tree.js

"use strict";
/**
 * Binary Search Tree
 *
 * @example
 * import { BinarySearchTree } from '../../ds/binary-search-tree';
 * const bst = new BinarySearchTree();
 * bst.insert(10);
 * bst.insert(5);
 * bst.insert(8);
 * bst.insert(4);
 * bst.insert(6);
 *
 * @author Gaurav Soni
 *
 * @module ds/binary-tree
 *
 */
Object.defineProperty(exports, "__esModule", { value: true });
exports.BinarySearchTree = 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 BinarySearchTree {
    constructor() {
        this.root = null;
    }
    /**
     * Insert the node into the binary 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 {T} value value that needs to be inserted
     * @param {TreeNode} 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 a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST
     * <br /><br />
     * For example,
     * <br />
     * <b>Input:</b> root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
     * <br />
     * <b>Output:</b> 6
     * <br />
     *
     * @static
     * @function
     * @see {@link https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/|Lowest Common Ancestor of a Binary Search Tree}
     *
     * @public
     *
     * @param {TreeNode} root root of binary search tree
     * @param {TreeNode} p First tree node
     * @param {TreeNode} q Second tree node
     *
     * @returns {number} Lowest common ancestor between two nodes
     */
    static lowestCommonAncestor(root, p, q) {
        function _lowestCommonAncestor(root, _p, _q) {
            if (!root)
                return;
            if (p.value < root.value && q.value < root.value) {
                return _lowestCommonAncestor(root.left, _p, _q);
            }
            else if (p.value > root.value && q.value > root.value) {
                return _lowestCommonAncestor(root.right, _p, _q);
            }
            else {
                return root.value;
            }
        }
        return _lowestCommonAncestor(root, p, q);
    }
}
exports.BinarySearchTree = BinarySearchTree;