Posts

Showing posts from June, 2025

Design Add and Search Words Data Structure

 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.   Example: Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord(...
Post a Comment
Read more

Implement Trie (Prefix Tree)

 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.   Example 1: Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true] Explanation Trie trie = new ...
Post a Comment
Read more

Maximum Level Sum of a Binary Tree

Image
 Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on. Return the smallest level x such that the sum of all the values of nodes at level x is maximal.   Example 1: Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation:  Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2. Example 2: Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] Output: 2   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *     ...
Post a Comment
Read more

Find Bottom Left Tree Value

Image
 Given the root of a binary tree, return the leftmost value in the last row of the tree.   Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6,null,null,7] Output: 7   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public int findBottomLeftValue ( TreeNode root ) {                   Queue < TreeNode > q = new LinkedList <>();     ...
Post a Comment
Read more

Binary Tree Right Side View

Image
 Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.   Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Explanation: Example 2: Input: root = [1,2,3,4,null,null,null,5] Output: [1,3,4,5] Explanation: Example 3: Input: root = [1,null,3] Output: [1,3] Example 4 Input: root = [] Output: [] import java.util.*; class Solution {     public ArrayList < Integer > rightView ( Node root ) {         ArrayList < Integer > result = new ArrayList <>();         if (root == null ) return result;         Queue < Node > q = new LinkedList <>();         q . offer (root);         while (! q . isEmpty ()) {             int size = q . size ();             for ( int i = 0...
Post a Comment
Read more

Left View of Binary Tree

 You are given the root of a binary tree. Your task is to return the left view of the binary tree. The left view of a binary tree is the set of nodes visible when the tree is viewed from the left side. If the tree is empty, return an empty list. Examples : Input: root[] = [1, 2, 3, 4, 5, N, N] Output: [1, 2, 4] Explanation: From the left side of the tree, only the nodes 1, 2, and 4 are visible. Input: root[] = [1, 2, 3, N, N, 4, N, N, 5, N, N] Output: [1, 2, 4, 5] Explanation: From the left side of the tree, the nodes 1, 2, 4, and 5 are visible. Input: root[] = [N] Output: [] Approach 1: Level Order Traversal (BFS) We can do a level-order traversal using a queue , and print the first node of each level . ✏️ Notes: Use a Queue<Node> for BFS (level order traversal). At each level: Get the number of nodes in that level: int size = q.size() Loop from i = 0 to i < size : If i == 0 → this is the first node at this level → add to result Add the left and rig...
Post a Comment
Read more

Path Sum III

Image
 Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).   Example 1: Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown. Example 2: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3   Constraints: The number of nodes in the tree is in the range [0, 1000]. -109 <= Node.val <= 109 -1000 <= targetSum <= 1000 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left...
Post a Comment
Read more

Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.   Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22 Example 2: Input: root = [1,2,3], targetSum = 5 Output: [] Example 3: Input: root = [1,2], targetSum = 0 Output: []   Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 Approach: DFS + Backtracking 🔸 Idea: Use DFS to traverse all paths from root to leaf. Maintain a current path ( List<Integer> ) and current sum. If at a leaf ...
Post a Comment
Read more

Sum Root to Leaf Numbers

Image
 You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path in the tree represents a number. For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer. A leaf node is a node with no children.   Example 1: Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25. Example 2: Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026.   Constraints: The number of nodes in the tree is in the range [1, 1000]. 0 <= Node.val <= 9 The depth of the tree w...
Post a Comment
Read more

Invert Binary Tree

Image
 Given the root of a binary tree, invert the tree, and return its root.   Example 1: Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2: Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: []   Constraints: The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public TreeNode invertTree ( TreeNode root ) {     ...
Post a Comment
Read more

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.   Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public boolean isBalanced ( TreeNode root ) {                 if (root == null ) return true ;         if ...
Post a Comment
Read more

Path Sum

Image
 Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.   Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths.   Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 🔄 Dry Run Step-by-Step (DFS Style): Call: hasPathSum(5, 22) Node = 5 Remaining = 22 - 5 = 17 Now explore both left...
Post a Comment
Read more

Symmetric Tree - Mirror Image

Image
  Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).   Example 1: Input: root = [1,2,2,3,4,4,3] Output: true Example 2: Input: root = [1,2,2,null,3,null,3] Output: false   Constraints: The number of nodes in the tree is in the range [1, 1000]. -100 <= Node.val <= 100   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public boolean isSymmetric ( TreeNode root ) { ...
Post a Comment
Read more