Leetcode Problem 600-699
DFS - Recursive
- if both nodes are null returns null.
- if one of the node null, return the other node.
- else Create new node with value = t1->val+t2->val.
- set new nodes left = merge(t1->left, t2->left)
- set new nodes right = merge(t1->right, t2->right)
- return new node;
Time complexity: O(n). A total of n nodes need to be traversed. Here, n represents the minimum number of nodes from the two given trees.
Space complexity: O(n). The depth of the recursion tree can go upto n in the case of a skewed tree. In average case, depth will be O(log n).
BFS - Iterative
- Base condition as in recursion
- Create 2 queues for BFS and push root nodes in them.
- While both queues are not empty
- Store the front nodes and Pop from both queues
- Add value of 2nd node in 1st
- if node1’s left is null and node2’s left is not null, then add node1’s left to node2’s left
- else if both’s left not null then push them in respective queues
- if node1’s right is null and node2’s right is not null, then add node1’s right to node2’s right
- else if both’s right not null then push them in respective queues.
Time complexity: O(n). A total of n nodes need to be traversed. Here, n represents the minimum number of nodes from the two given trees.
Space complexity: O(n). The size of queue can go upto n in the case of a skewed tree.
MUST READ:
This question is in continuation with A general approach to level order traversal questions series.
Previous Questions
- Binary tree level order traversal
- Binary tree level order traversal - II
- Binary tree zig-zag level order traversal
Recursive Solution
- Here we need to keep track of the sum of level and count of nodes so we can calculate the average.
- On every level we increment the level count and add the value of the node to the sum.
- If we encounter new level (
level==levelSum.size()) we push new values(0.0) in the sum and count vectors.
- We do it recursively for left and right subtrees with increasing level count.
- Finally we can calculate average by dividing sum by count for each list.
Iterative Solution
- This solution is so same as the first question of level order traversal.
- Here we just keep track of sum at current level instead of pushing node in level vector which we did in first question.
- At last we divide sum by size of the queue (i.e. count of nodes in current level).
Iterative Solution
- Converted recursive solution to iterative.
- This solution involves 2 extra vectors which add up to the our additional use space.
O(N) Time and O(N) space
- This method also works for those who are not BSTs.
- The idea is to use a hashtable to save the values of the nodes in the BST. Each time when we insert the value of a new node into the hashtable, we check if the hashtable contains k - node.val.
O(N) Time and O(N) space
- The idea is to use a sorted array to save the values of the nodes in the BST by using an inorder traversal.
- Then, we use two pointers which begins from the start and end of the array to find if there is a sum k.
O(hn) Time and O(h) space
h is the height of the tree, which is log n at best case, and n at worst case.- The idea is to use binary search method.
- For each node, we check if k - node.val exists in this BST.
BFS
DFS
- Int will give integer overflow.
Brute Force
- We create a 2D matrix of multiplication table then convert it to a 1D array.
- We sort the array and return the
kth element.
- TC: O(N^2)
- SC: O(M*N)+O(M+N)- For extra 2D and 1D arrays.
Brute force with reduced space
- Instead of creating a 2D array, we can create a 1D array of size
m+n and fill it with the multiplication table.
- Then We sort the array and return the
kth element.
- TC: O(N^2)
- SC: O(M+N)- For 1D array.
Stack Solution
- Simple simulation using stack.
DFS - Recursive
BFS - Iterative