Tree-Ds

Problem Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height balanced BST: a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Examples Example 1: Input: nums = [1, 2, 3, 4, 5, 6] Output: [3,2,5,1,null,4,6] Explanation: [4,2,5,1,3,null,6] is also accepted. ...

Problem Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix. For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries. Solution Method 1 - Using Trie with map of children and DFS Trie Class We have already seen Map-based Trie Implementation, and also seen another implementation of trie here: Implement Trie Problem. ...

Problem Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. Examples Example 1: Input: nums = [1, 2, 3, 4, 5, 6] Output: [3,2,5,1,null,4,6] Explanation: [4,2,5,1,3,null,6] is also accepted. ...

Problem A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise. Examples Example 1: ...

Problem Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter. Examples Example 1: ...