Today I have solved the problem in javascript

 A ternary search tree is a trie-like data structure where each node may have up to three children. Here is an example which represents the words code, cob, be, ax, war, and we.


       c

    /  |  \

   b   o   w

 / |   |   |

a  e   d   a

|    / |   | \ 

x   b  e   r  e

The tree is structured according to the following rules:


left child nodes link to words lexicographically earlier than the parent prefix

right child nodes link to words lexicographically later than the parent prefix

middle child nodes continue the current word

For instance, since code is the first word inserted in the tree, and cob lexicographically precedes cod, cob is represented as a left child extending from cod.


Implement insertion and search functions for a ternary search tree.

const tree = { root: null };

const words = ["code", "cob", "be", "ax", "war", "we"];


words.forEach((word) => insert(tree, word));

function createNode(val) {

  return { val, left: null, middle: null, right: null, isEnd: false };

}


function insert(tree, word, node = tree) {

  if (!tree.root) {

    tree.root = createNode(word[0]);

    insert(tree, word.slice(1), tree.root);

  } else {

    const char = word[0];

    if (char < node.val) {

      if (!node.left) node.left = createNode(char);

      insert(tree, word, node.left);

    } else if (char > node.val) {

      if (!node.right) node.right = createNode(char);

      insert(tree, word, node.right);

    } else {

      if (word.length > 1) {

        if (!node.middle) node.middle = createNode(word[1]);

        insert(tree, word.slice(1), node.middle);

      } else {

        node.isEnd = true;

      }

    }

  }

}


function search(tree, word, node = tree.root) {

  if (!node) return false;


  const char = word[0];

  if (char < node.val) {

    return search(tree, word, node.left);

  } else if (char > node.val) {

    return search(tree, word, node.right);

  } else {

    if (word.length > 1) {

      return search(tree, word.slice(1), node.middle);

    } else {

      return node.isEnd;

    }

  }

}

console.log(search(tree, "code")); 

console.log(search(tree, "cob"));

console.log(search(tree, "bat")); 

Output:

false
false
false



Comments

Post a Comment

Popular posts from this blog

Building a Full-Stack Student Management System with React.js and NestJS

  🚀 My Journey Creating a Student Management System 🌟 I'm excited to share my recent project — a Student Management System ! This project gave me hands-on experience in building a full-stack application, enhancing both my frontend and backend development skills. 💡 Project Overview The Student Management System is designed to help educational institutions efficiently manage student data, including enrollment, attendance, and performance. The goal was to create a user-friendly platform for both students and administrators. 🔨 Tech Stack Used ✅ Frontend: JavaScript, HTML, CSS, React.js ✅ Backend: TypeScript, NestJS, Node.js ✅ Database: MongoDB (with _id for unique identifiers) 🌟 Key Features ✔️ Student Registration – Easy registration with unique ID management ✔️ Attendance Tracking – Real-time updates on student attendance ✔️ Performance Reports – Generate and view student performance reports ✔️ Admin Panel – Secure access for administrators to manage student...
Read more

Today I have solved the problem in javascript

 Consider the following scenario: there are N mice and N holes placed at integer points along a line. Given this, find a method that maps mice to holes such that the largest number of steps any mouse takes is minimized.Each move consists of moving one mouse one unit to the left or right, and only one mouse can fit inside each hole.For example, suppose the mice are positioned at [1, 4, 9, 15], and the holes are located at [10, -5, 0, 16]. In this case, the best pairing would require us to send the mouse at 1 to the hole at -5, so our function should return 6. const mice = [1, 4, 9, 15]; const holes = [10, -5, 0, 16]; function minSteps(mice, holes) {    mice.sort((a, b) => a - b);     holes.sort((a, b) => a - b); let maxSteps = 0;     for (let i = 0; i < mice.length; i++) {         let steps = Math.abs(mice[i] - holes[i]);         if (steps > maxSteps) {             maxStep...
Read more

Today I have solved problem in javascript

 You are given an array X of floating-point numbers x1, x2, ... xn. These can be rounded up or down to create a corresponding array Y of integers y1, y2, ... yn. Write an algorithm that finds an appropriate Y array with the following properties: The rounded sums of both arrays should be equal. The absolute pairwise difference between elements is minimized. In other words, |x1- y1| + |x2- y2| + ... + |xn- yn| should be as small as possible. For example, suppose your input is [1.3, 2.3, 4.4]. In this case you cannot do better than [1, 2, 5], which has an absolute difference of |1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1. const inputArray = [1.3, 2.3, 4.4]; const resultArray = roundArray(inputArray); function roundArray(inputArray) {     const n = inputArray.length;     const roundedArray = [];     let roundedSum = 0; for (let i = 0; i < n; i++) {         consat roundedValue = Math.round(inputArray[i]);         rounded...
Read more