Problems
September 5, 2022
Single number III
We will be using the XOR trick i.e n^n=0. During first traversal we will get the XOR of the required two numbers, then we will get the least significant bit of the XOR operation. This...
September 5, 2022
Sort list
We will use standard merge sort to sort the list, to get the middle node, we will use a fast and slow pointer approach, rest is standard merge sort stuffs.
Time Complexity: O(nlog(n))...
September 4, 2022
Amount of time for binary tree to be infected
We will first create an adjacency list for our tree. Then we run a simple BFS to traverse all the nodes, and the number of level we need to traverse is our time.
Time Complexity: O(n)...
September 4, 2022
Binary search tree iterator
We will create a queue to store our values while create the oterator class. Then for next, we will pop the values from the queue and return, for hasNext, we will check it the queue is empty or not....
ReadSeptember 4, 2022
Binary tree level order traversal II
This is a classing BFS problem. We should traverse the whole tree with BFS, and store the values level by level to a list. Then combine each level to a list and return the reversed list as result....
ReadSeptember 4, 2022
Binary tree zigzag level order traversal
We will traverse the tree with BFS and append the values of each level to our result list. And for each alternative level we change the order. Finally return the result after we visit each node....
ReadSeptember 4, 2022
Construct binary tree from inorder and postorder traversal
We know, the last index of postorder traversal is always the root of the tree, from that info, we can find the root in inorder traversal too. From there, we will find the left inorder subtree and...
ReadSeptember 4, 2022
Convert sorted list to binary search tree
We will first loop over the entire linked list and add the values to a list. Now we will take the middle index of the list as our root and recursively build both the left and right subtree and return...
ReadSeptember 4, 2022
Count complete tree nodes
We will count the height of the left and right subtree. If they are equal, then the it's a complete tree, so the number of node will be 2^n-1. If it's not a complete tree, then the...
September 4, 2022
delete-node-in-a-bst
We will check whether the key is greater than root, then the key is in right subtree, if the key is less than root, then key is in left subtree. If the key is the root, then we check, if there is a...
Read