2025 July 19 Problems

66 views
Skip to first unread message

daryl...@gmail.com

unread,
Jul 19, 2025, 12:39:35 PMJul 19
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.


669. Trim a Binary Search Tree Medium 66.4%



Please download and import the following iCalendar (.ics) files to your calendar system.

daryl...@gmail.com

unread,
Jul 19, 2025, 1:55:42 PMJul 19
to leetcode-meetup
669. Trim a Binary Search Tree Medium 66.4%

Basic recursive solution. We'll return None if root is None, to making checking empty nodes easier in the rest of the problem.
If the current node is lower than low, then we'll have to replace it with whatever remains of the right subtree after trimming. We can ignore the entire left subtree of the original node since they all have to be lower than low as well.
Similarly, if the current node is higher than high we'll replace it with the root of the trimmed left subtree and ignore the right subtree of the original node.
If the root node didn't change we can recursively trim both the children.

O(n) time
O(n) space, mostly from worst case call stack size

def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
if root.val < low:
root = self.trimBST(root.right, low, high)
elif root.val > high:
root = self.trimBST(root.left, low, high)
else:
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
Message has been deleted

FloM

unread,
Jul 19, 2025, 2:12:40 PMJul 19
to leetcode-meetup
669. Trim a Binary Search Tree Medium
Already had done problem. Time: O(number of nodes), Mem: O(n)
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if ( root == nullptr)
{
return root;
}

if (root->val > high)
{
return trimBST(root->left, low, high);
}

if (root->val < low)
{
return trimBST(root->right, low, high);
}

if (root->val == high)
{
root->right = nullptr;
}
else
{
root->right = trimBST(root->right, low, high);
}
if (root->val == low)
{
root->left = nullptr;
}
else
{
root->left = trimBST(root->left, low, high);
}

return root;

}
};
On Saturday, July 19, 2025 at 11:09:09 AM UTC-7 FloM wrote:
208. Implement Trie (Prefix Tree) Medium
class Trie {
public:

struct Node
{
vector<shared_ptr<Node>> nodes(26, nullptr);
char letter = '-';
string str{};
};

Trie() {}
void insert(string word) {
int firstLetterInt = word[0] - 'a';

if (!root.nodes[firstLetterInt])
{
root.nodes[firstLetterInt] = make_shared<Node>();
}
insert(word, 0, root.nodes[firstLetterInt]);
}

// Assumes curNode is not nullptr.
void insert(string word, int idx, shared_ptr<Node> curNode)
{
if (curNode->letter == '-')
{
curNode->letter = word[idx];
}

if (word.size()-1 == idx)
{
curNode->str = word;
}
else
{
int nextLetterInt = word[idx+1] - 'a';
if (!curNode->nodes.contains(nextLetterInt))
{
curNode->nodes[nextLetterInt] = make_shared<Node>();
}
insert(word, idx+1, curNode->nodes[nextLetterInt]);
}
}
bool search(string word) {
int firstLetterInt = word[0] - 'a';

if(root.nodes.contains(firstLetterInt))
{
return search(word, 0, root.nodes[firstLetterInt]);
}
return false;
}

bool search(string word, int idx, shared_ptr<Node> curNode)
{
if( (idx == word.size()-1) && (curNode->str == word) )
{
return true;
}
else
{
int nextLetterInt = word[idx+1] - 'a';
if(curNode->nodes.contains(nextLetterInt))
{
return search(word, idx+1, curNode->nodes[nextLetterInt]);
}
}
return false;

}
bool startsWith(string prefix) {
int firstLetterInt = prefix[0] - 'a';

if(root.nodes.contains(firstLetterInt))
{
return startsWith(prefix, 0, root.nodes[firstLetterInt]);
}
return false;
}

bool startsWith(string word, int idx, shared_ptr<Node> curNode)
{
if( idx == (word.size()-1))
{
return true;
}
else
{
int nextLetterInt = word[idx+1] - 'a';
if(curNode->nodes.contains(nextLetterInt))
{
return startsWith(word, idx+1, curNode->nodes[nextLetterInt]);
}
}
return false;
}

Node root{};


};

FloM

unread,
Jul 19, 2025, 2:24:23 PMJul 19
to leetcode-meetup
208. Implement Trie (Prefix Tree) Medium
class Trie {
public:

struct Node
{
unordered_map<int, shared_ptr<Node>> nodes{};
char letter = '-';
string str{};
};

Trie() {
}
void insert(string word) {
int firstLetterInt = word[0] - 'a';

if(!root.nodes.contains(firstLetterInt))

Sharad Bagri

unread,
Jul 19, 2025, 2:29:58 PMJul 19
to leetcode-meetup
On Saturday, July 19, 2025 at 9:39:35 AM UTC-7 daryl...@gmail.com wrote:
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.


class Node:
def __init__(self):
self.child = dict()
self.is_end = False
def insert_char(self, char):
self.child[char] = Node()
return self.child[char]

def set_end(self):
self.is_end=True

def search_char(self, char):
if char in self.child:
return self.child[char]
else:
return None

class Trie:
def __init__(self):
self.root = Node()
print(f'type self.root {type(self.root)}')

def insert(self, word: str) -> None:
node = self.root
for a_char in word:
if a_char in node.child:
node = node.child[a_char]
continue
else:
node = node.insert_char(a_char)
node.set_end()

def search(self, word: str) -> bool:
node = self.root
for a_char in word:
if a_char in node.child:
node = node.child[a_char]
else:
return False
return node.is_end == True

def startsWith(self, prefix: str) -> bool:
node = self.root
for a_char in prefix:
if a_char in node.child:
node = node.child[a_char]
else:
return False
return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix) 

Sourabh Majumdar

unread,
Jul 19, 2025, 2:30:35 PMJul 19
to leetcode-meetup

Implementation of Trie
class Trie {
public:
struct TrieNode{
std::unordered_map<char, TrieNode*> map;
bool is_end_of_word;
};

TrieNode* root = nullptr;
Trie() {
root = new TrieNode;
root->is_end_of_word = false;
}
void insert(string word) {
TrieNode* iter_node = root;
for(auto character : word) {
if (!iter_node->map.contains(character)) {
iter_node->map[character] = new TrieNode;
iter_node->map[character]->is_end_of_word = false;
}

iter_node = iter_node->map[character];
}

iter_node->is_end_of_word = true;
}
bool search(string word) {
TrieNode* iter_node = root;
for(auto character : word) {
if (!iter_node->map.contains(character)) {
return false;
}

iter_node = iter_node->map[character];
}

return iter_node->is_end_of_word;
}
bool startsWith(string prefix) {
// check if we can traverse without breaking anything.
TrieNode* iter_node = root;
for(auto character : prefix) {
if (!iter_node->map.contains(character)) {
return false;
}

iter_node = iter_node->map[character];
}

return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/

Sourabh Majumdar

unread,
Jul 19, 2025, 2:31:02 PMJul 19
to leetcode-meetup
Trim BST
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
return nullptr;
}

// Then prune the left and the right
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);

// now if root->val is low then return right
if (root->val < low) {
return root->right;
}

if (root->val > high) {
return root->left;
}

return root;
}
};

daryl...@gmail.com

unread,
Jul 19, 2025, 2:54:52 PMJul 19
to leetcode-meetup
208. Implement Trie (Prefix Tree) Medium 68.1%

Go implementation of Trie. The short description is a Trie is a tree where each node is a letter, and the children are the possible letters that might follow the current letter. A word is represented by walking down the tree from the starting node, following the letters of the word. To deal with words that might be prefixes of each other such as "app" and "apple", we have a marker for each node to determine whether it's the end of a word. For the Search function we need to end on a node with this marker set, whereas for the StartsWith we don't care either way.
O(sum of all word lengths) space
O(length of word) time for insert and both search operations.

type Trie struct {
children map[rune]*Trie
terminal bool
}


func Constructor() Trie {
trie := Trie{
children: make(map[rune]*Trie),
}
return trie
}


func (this *Trie) Insert(word string) {
trie := this
for _, rune := range word {
next, ok := trie.children[rune]
if !ok {
newTrie := Constructor()
next = &newTrie
trie.children[rune] = next
}
trie = next
}
trie.terminal = true
}


func (this *Trie) Search(word string) bool {
trie := this
for _, rune := range word {
next, ok := trie.children[rune]
if !ok {
return false
}
trie = next
}
return trie.terminal
}


func (this *Trie) StartsWith(prefix string) bool {
trie := this
for _, rune := range prefix {
next, ok := trie.children[rune]
if !ok {
return false
}
trie = next
}
return true
}

On Saturday, July 19, 2025 at 9:39:35 AM UTC-7 daryl...@gmail.com wrote:

vinay

unread,
Jul 22, 2025, 1:47:15 PMJul 22
to leetcod...@googlegroups.com
669. Trim a Binary Search Tree Medium 66.4%

If the current node's value is less than the lower bound, we can discard the entire left subtree since it falls out of bounds anyway and recursively process the right subtree. 
Similarly, if the node's value exceeds the upper bound,  we can discard  the right subtree and processes the left subtree. 
For nodes within the valid range, we can recursively trim both left and right subtrees and return the current node as the new root of the trimmed subtree.

time: o(N)
space: o(h)


class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {

        if(root == null){
            return root;
        }
       
        if(root.val < low){
            return trimBST(root.right, low, high);
        }
        if(root.val > high){
            return trimBST(root.left, low, high);
        }

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
       
       
    }
}

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/leetcode-meetup/302535de-f7d4-4543-9782-d80fffdb70b4n%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages