import {BST, BSTNode} from 'data-structure-typed';
// /* or if you prefer */ import {BST, BSTNode} from 'bst-typed';

const bst = new BST();
bst instanceof BST;                    // true
bst.add(11);
bst.add(3);
const idsAndValues = [15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
bst.addMany(idsAndValues);
bst.root instanceof BSTNode;           // true

if (bst.root) bst.root.id;             // 11

bst.size;                              // 16

bst.has(6);                            // true

const node6 = bst.get(6);
node6 && bst.getHeight(6);             // 2
node6 && bst.getDepth(6);              // 3

const nodeId10 = bst.get(10);
nodeId10?.id;                          // 10

const nodeVal9 = bst.get(9, 'val');
nodeVal9?.id;                          // 9


const leftMost = bst.getLeftMost();
leftMost?.id;                          // 1

const node15 = bst.get(15);
const minNodeBySpecificNode = node15 && bst.getLeftMost(node15);
minNodeBySpecificNode?.id;             // 12

const subTreeSum = node15 && bst.subTreeSum(15);
subTreeSum;                            // 70

const lesserSum = bst.lesserSum(10);
lesserSum;                             // 45

node15 instanceof BSTNode;             // true

const node11 = bst.get(11);
node11 instanceof BSTNode;             // true

const dfsInorderNodes = bst.DFS('in', 'node');
dfsInorderNodes[0].id;                 // 1
dfsInorderNodes[dfsInorderNodes.length - 1].id;            // 16

bst.perfectlyBalance();
bst.isPerfectlyBalanced();                                  // true

const bfsNodesAfterBalanced = bst.BFS('node');
bfsNodesAfterBalanced[0].id;                                // 8);
bfsNodesAfterBalanced[bfsNodesAfterBalanced.length - 1].id; // 16

const removed11 = bst.remove(11, true);
removed11 instanceof Array;                                 // true


if (removed11[0].deleted) removed11[0].deleted.id;          // 11

bst.isAVLBalanced();                                        // true

bst.getHeight(15);                                          // 1

const removed1 = bst.remove(1, true);
removed1 instanceof Array; // true

if (removed1[0].deleted) removed1[0].deleted.id;            // 1

bst.isAVLBalanced();                                        // true

bst.getHeight();                                            // 4

const removed4 = bst.remove(4, true);
removed4 instanceof Array;                                   // true

if (removed4[0].deleted) removed4[0].deleted.id;            // 4
bst.isAVLBalanced();                                        // true
bst.getHeight();                                            // 4

const removed10 = bst.remove(10, true);

if (removed10[0].deleted) removed10[0].deleted.id;           // 10
bst.isAVLBalanced();                                         // false
bst.getHeight();                                             // 4

const removed15 = bst.remove(15, true);

if (removed15[0].deleted) removed15[0].deleted.id;           // 15

bst.isAVLBalanced();                                         // true
bst.getHeight();                                             // 3

const removed5 = bst.remove(5, true);

if (removed5[0].deleted) removed5[0].deleted.id;              // 5

bst.isAVLBalanced();                                          // true
bst.getHeight();                                              // 3

const removed13 = bst.remove(13, true);
if (removed13[0].deleted) removed13[0].deleted.id;            // 13
bst.isAVLBalanced();                                          // true
bst.getHeight();                                              // 3

const removed3 = bst.remove(3, true);
if (removed3[0].deleted) removed3[0].deleted.id;               // 3
bst.isAVLBalanced();                                           // false
bst.getHeight();                                               // 3

const removed8 = bst.remove(8, true);
if (removed8[0].deleted) removed8[0].deleted.id;               // 8
bst.isAVLBalanced();                                           // true
bst.getHeight();                                               // 3

const removed6 = bst.remove(6, true);
if (removed6[0].deleted) removed6[0].deleted.id;               // 6
bst.remove(6, true).length;                                    // 0
bst.isAVLBalanced();                                           // false
bst.getHeight();                                               // 3

const removed7 = bst.remove(7, true);
if (removed7[0].deleted) removed7[0].deleted.id;               // 7
bst.isAVLBalanced();                                           // false
bst.getHeight();                                               // 3

const removed9 = bst.remove(9, true);
if (removed9[0].deleted) removed9[0].deleted.id;               // 9
bst.isAVLBalanced();                                           // false
bst.getHeight();                                               // 3

const removed14 = bst.remove(14, true);
if (removed14[0].deleted) removed14[0].deleted.id;             // 14
bst.isAVLBalanced();                                           // false
bst.getHeight();                                               // 2

bst.isAVLBalanced();                                           // false

const bfsIDs = bst.BFS();
bfsIDs[0];                                                     // 2
bfsIDs[1];                                                     // 12
bfsIDs[2];                                                     // 16

const bfsNodes = bst.BFS('node');
bfsNodes[0].id;                                                // 2
bfsNodes[1].id;                                                // 12
bfsNodes[2].id;                                                // 16

 const bst = new BST<number>([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);

    // Delete a leaf node
    bst.delete(1);
    console.log(bst.has(1)); // false;

    // Delete a node with one child
    bst.delete(2);
    console.log(bst.has(2)); // false;

    // Delete a node with two children
    bst.delete(3);
    console.log(bst.has(3)); // false;

    // Size decreases with each deletion
    console.log(bst.size); // 13;

    // Other nodes remain searchable
    console.log(bst.has(11)); // true;
    console.log(bst.has(15)); // true;

 const dataset1 = new BST<number, string>([
      [1, 'A'],
      [7, 'G']
    ]);
    const dataset2 = [
      [2, 'B'],
      [6, 'F']
    ];
    const dataset3 = new BST<number, string>([
      [3, 'C'],
      [5, 'E'],
      [4, 'D']
    ]);

    // Merge datasets into a single BinarySearchTree
    const merged = new BST<number, string>(dataset1);
    merged.setMany(dataset2);
    merged.merge(dataset3);

    // Verify merged dataset is in sorted order
    console.log([...merged.values()]); // ['A', 'B', 'C', 'D', 'E', 'F', 'G'];

 interface Expression {
      id: number;
      operator: string;
      precedence: number;
    }

    // BST efficiently stores and retrieves operators by precedence
    const operatorTree = new BST<number, Expression>(
      [
        [1, { id: 1, operator: '+', precedence: 1 }],
        [2, { id: 2, operator: '*', precedence: 2 }],
        [3, { id: 3, operator: '/', precedence: 2 }],
        [4, { id: 4, operator: '-', precedence: 1 }],
        [5, { id: 5, operator: '^', precedence: 3 }]
      ],
      { isMapMode: false }
    );

    console.log(operatorTree.size); // 5;

    // Quick lookup of operators
    const mult = operatorTree.get(2);
    console.log(mult?.operator); // '*';
    console.log(mult?.precedence); // 2;

    // Check if operator exists
    console.log(operatorTree.has(5)); // true;
    console.log(operatorTree.has(99)); // false;

    // Retrieve operator by precedence level
    const expNode = operatorTree.getNode(3);
    console.log(expNode?.key); // 3;
    console.log(expNode?.value?.precedence); // 2;

    // Delete operator and verify
    operatorTree.delete(1);
    console.log(operatorTree.has(1)); // false;
    console.log(operatorTree.size); // 4;

    // Get tree height for optimization analysis
    const treeHeight = operatorTree.getHeight();
    console.log(treeHeight); // > 0;

    // Remaining operators are still accessible
    const remaining = operatorTree.get(2);
    console.log(remaining); // defined;

 const bst = new BST<number>([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]);

    // LCA helper function
    const findLCA = (num1: number, num2: number): number | undefined => {
      const path1 = bst.getPathToRoot(num1);
      const path2 = bst.getPathToRoot(num2);
      // Find the first common ancestor
      return findFirstCommon(path1, path2);
    };

    function findFirstCommon(arr1: (number | undefined)[], arr2: (number | undefined)[]): number | undefined {
      for (const num of arr1) {
        if (arr2.indexOf(num) !== -1) {
          return num;
        }
      }
      return undefined;
    }

    // Assertions
    console.log(findLCA(3, 10)); // 7;
    console.log(findLCA(5, 35)); // 15;
    console.log(findLCA(20, 30)); // 25;