DFS Flashcards
- Deepest Leaves Sum
Given the root of a binary tree, return the sum of values of its deepest leaves.
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
/**
* 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 {
Queue<TreeNode> q = new LinkedList<>();
Map<Integer,List<TreeNode>> hm = new TreeMap<>();
public int deepestLeavesSum(TreeNode root) {
//Base condition
if(root.left == null && root.right == null){
return root.val;
}
q.add(root);
int level = 1;
while(!q.isEmpty()){
int size = q.size();
for(int i=0;i<size;i++){
TreeNode curr= q.poll();
if(hm.containsKey(level)){
hm.get(level).add(curr);
}
else{
hm.put(level,new ArrayList<>());
hm.get(level).add(curr);
}
if( curr.left != null) q.add(curr.left);
if(curr.right != null) q.add(curr.right);
}
level++;
}
int maxElement = 0;
Set<Integer> keys = hm.keySet();
for(int i : keys){
maxElement = Math.max(i, maxElement);
}
List<TreeNode> listNode = hm.get(maxElement);
int output =0;
for(TreeNode n : listNode ){
output+=n.val;
}
return output;
} }
- Sum of Nodes with Even-Valued Grandparent
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
/**
* 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 {
int globalSum =0;
public int sumEvenGrandparent(TreeNode root) {
dfs(root);
return globalSum;
}
private void dfs(TreeNode root){
if(root == null) return ;
if(root.val % 2 == 0){
if(root.left != null){
if(root.left.left != null) globalSum+= root.left.left.val;
if(root.left.right != null) globalSum+= root.left.right.val;
}
if(root.right != null){
if(root.right.left != null) globalSum+= root.right.left.val;
if(root.right.right != null) globalSum+= root.right.right.val;
}
}
dfs(root.left);
dfs(root.right);
} }
- Range Sum of BST
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
class Solution {
int output = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
if(root == null) return 0;
if(root.val >= low && root.val <= high) output += root.val;
rangeSumBST(root.left, low, high);
rangeSumBST(root.right, low, high);
return output;
} }
- Find All The Lonely Nodes
Solved
Easy
Topics
Companies
Hint
In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node.
Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.
Example 1:
/**
* 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 {
List<Integer> output = new ArrayList<>();
public List<Integer> getLonelyNodes(TreeNode root) {</Integer></Integer>
if(root == null) return output;
if(root.left == null && root.right != null) output.add(root.right.val);
if(root.right == null && root.left != null) output.add(root.left.val);
getLonelyNodes(root.left);
getLonelyNodes(root.right);
return output;
} }
- Merge Two Binary Trees
Solved
Easy
Topics
Companies
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
/**
* 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 mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) return root2;
if(root2 == null) return root1;
root1.val = root1.val + root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right =mergeTrees(root1.right, root2.right);
return root1;
}
}
- Evaluate Boolean Binary Tree
Solved
Easy
Topics
Companies
Hint
You are given the root of a full binary tree with the following properties:
Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.
The evaluation of a node is as follows:
If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.
Return the boolean result of evaluating the root node.
A full binary tree is a binary tree where each node has either 0 or 2 children.
A leaf node is a node that has zero children.
/**
* 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 evaluateTree(TreeNode root) {
if(root.val == 1) return true;
else if(root.val == 0) return false;
else if(root.val == 2){
return evaluateTree(root.left) || evaluateTree(root.right);
}
else{
return evaluateTree(root.left) && evaluateTree(root.right);
}
} }
- Invert Binary tree
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:
/**
* 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) {
if(root != null){
TreeNode left = invertTree(root.left);
root.left = invertTree(root.right);
root.right=left;
}
return root;
} }
- Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
} }
- Sum of Root To Leaf Binary Numbers
Solved
Easy
Topics
Companies
Hint
You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.
For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0]
Output: 0
/**
* 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 {
int sum =0;
public int sumRootToLeaf(TreeNode root) {
dfs(root,""+root.val);
return sum;
}
private void dfs(TreeNode root, String str){
if(root.left == null && root.right == null){
sum+=Integer.parseInt(str,2);
}
if(root.left != null){
dfs(root.left, str+root.left.val);
}
if(root.right != null){
dfs(root.right, str+root.right.val);
}
} }
- Univalued Binary Tree
A binary tree is uni-valued if every node in the tree has the same value.
Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.
Input: root = [1,1,1,1,1,null,1]
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 isUnivalTree(TreeNode root) {
int val = root.val;
return dfs(root,val);
}
private boolean dfs(TreeNode root, int val){
if(root == null) return true;
if(root.val != val) return false;
return (dfs(root.left, val) &&
dfs(root.right, val));
} }
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn’t have “lakes”, meaning the water inside isn’t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
class Solution {
public int islandPerimeter(int[][] grid) {
int r = grid.length;
int c = grid[0].length;
int sum =0;
for(int i=0; i< r; i++){
for(int j=0; j<c;j++){
if(grid[i][j] == 1) {
sum = sum+4;
if(i>0 && grid[i-1][j]==1) sum= sum-2;
if(j>0 && grid[i][j-1]==1 ) sum = sum-2;
}
}
}
return sum;
} }
