Category: Data Structures
-
Convert Roman to Integer
Given a string representing a roman numeral , convert it into an integer. The values of each roman character is also given: Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, IV means 4 XX means 20 Try out the solution here: https://leetcode.com/problems/roman-to-integer/ Solution: Have a…
-
Add two numbers represented by Linked List
Given two numbers represented by a linked list in reverse order. You have two linked lists. Each of them represent a number which is not empty and not negative. Each of the node in the linked lists represent a single digit. The numbers are linked in reverse order. Create a linked list with their sum…
-
Serialize and Deserialize a Tree
Given the root node of a tree , serialize it into a string. Given a serialized string , construct a tree and return the true node. Try out the solution here: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/ Solution: Serialization: First do a preorder traversal of the tree and store the node values in a string. If node is null store…
-
Word Search II
Given a m*n board of letters and a list of words , find those words present in the board. For example, Given the board: and the below list of words: [“oath”,”pea”,”eat”,”rain”] The output is “eat” ,”oauth” Try out the solution here: https://leetcode.com/problems/word-search-ii/solution/ Solution: Let’s use Trie data structure to solve this problem. We could use…
-
A Word dictionary for adding and searching words
Create a word dictionary to add and search words. You can also search using ‘.’ regular expression, That is searching for the word “.at” will return true if the dictionary contains words like cat , mat etc since the first letter can be anything. Try out the solution here: https://leetcode.com/problems/design-add-and-search-words-data-structure/ Solution: The solution to this…
-
How to implement Trie Data Structure?
Trie is a datastructure useful to store set of words. It is a tree with a lot of children , one for each letter of the alphabets. So if you want to store lower case English letter words each node can have unto 26 child nodes. Every word is represented by as many nodes as…
-
Find the Lowest Common Ancestor of two given nodes of a Binary Search Tree
Given two nodes and the root node of a binary search tree, Find the lowest common ancestor of those two nodes. A common ancestor node is a node who is the parent of both the given nodes. Lowest common ancestor means there is no other common ancestor node which is lower than this node in…
-
Kth Smallest Element in a Binary Search Tree
Given a binary search tree, find the kth smallest element in it. For example, For the below tree: If k = 3, Then the kth (3rd) smallest element is 3. If k = 2, Then the output is 2. Try out the solution here: https://leetcode.com/problems/kth-smallest-element-in-a-bst/ Solution: Hint : Use inorder traversal. Explanation: Approach 1 –…
-
Construct Binary Tree From Preorder and Inorder Traversals
Given the preorder and inorder traversal arrays of a tree, construct it. For example, Given preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] You need to construct the below tree: you need to return the root node of the above tree in your code. Try it here: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Solution: Hint: Using root node from preorder traversal ,…
-
Valid Binary Search Tree (BST) or not?
You are given a binary search tree. You need to find out if it is valid or not. A BST is valid if all the elements in the left tree are less than the current node And all the elements in the right tree are greater than the current node. This has to apply for…
