14 Java Intermediate Level Tree Interview Questions & Answers
Below is a list of our Java Intermediate Level Tree interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Is the binary tree symmetric?
This interview question concentrates on using Java recursive and iterative functions.
You are given a binary tree. You have to check if the tree is symmetric about its center.
A tree is symmetric when the left subtree and the right subtree of the root node are mirror images of each other as shown in the example below.
/*Example*/
10
/ |\
15 | 15
/ \ | / \
1 2 | 2 1
The above tree is symmetric about its center. So we will return true.
10
/ |\
1 | 1
/ \ | \
2 | 2
The above tree is not symmetric about its center. So we will return false.
Solution:
Approach I (Recursive):
For two nodes to be a mirror of each other, either they both should be non-null or both null. If only one of them is null, they are definitely not a mirror of each other.
If the nodes are non-null,
1. their value must be equal,
2. the left subtree of the first node must be the mirror of the right subtree of the second node,
3. the right subtree of the first node must be the mirror of the left subtree of the second 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) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) return true;
if (node1 == null || node2 == null) return false;
return(
node1.val == node2.val &&
isMirror(node1.left, node2.right) &&
isMirror(node1.right, node2.left));
}
}
Time complexity- O(number of nodes)
Space complexity- O(height of tree)
Approach II (Iterative):
The approach is almost the same as the recursive approach. We just use stack instead of recursion to keep track of nodes that we want to compare to check if they mirror each other.
We maintain a stack array. First, we push two nodes left and right of the root node. Then in every iteration, we pop two nodes from the stack. Then we check the null-ness of both nodes. If they both are null, we continue two check other nodes in the stack.
If only one of them is null, we straightway return false.
Then we compare their value. If values are equal, we push their children nodes in a specific order as with the recursive approach.
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) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root.left);
stack.push(root.right);
while(!stack.empty()) {
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
if (node1 == null && node2 == null) continue;
if (node1 == null || node2 == null) return false;
if (node1.val != node2.val) return false;
stack.push(node1.left);
stack.push(node2.right);
stack.push(node1.right);
stack.push(node2.left);
}
return true;
}
}
Time complexity- O(number of nodes)
Space complexity- O(height of tree)
Written by S. Kumar on June 27th, 2021
2. Can you merge binary trees?
This interview question concentrates on using Java recursive function.
You are given root nodes root1 and root2 of two binary trees. Your task to merge them to form a new binary tree. The merge rules are as follows-
1. if both the trees have nodes at a specific position, the merged tree will have a node with a value equal to the sum of those two nodes at that position.
root1- 1 root2- 4
/ \ / \
2 3 5 6
merged- 5
/ \
7 9
At position “rootâ€- both trees have nodes. So node in the merged tree has value 1 + 4 = 5
At position “left of the rootâ€- both trees have nodes. So node in the merged tree has value 2 + 5 = 7
At position “right of the rootâ€- both trees have nodes. So node in the merged tree has value 3 + 6 = 9
2. if one tree has null and the other tree has a node at a specific position. the merged tree will have a node with a value equal to the value of the node of the other tree.
root1- 1 root2- 4
/ \
2 6
merged- 5
/ \
2 6
At position “left of the rootâ€- root1 has a node with value 2 but root2 doesn’t have a node. The merged tree has 2 at that position.
At position “right of the rootâ€- root2 has a node with value 6 but root1 doesn’t have a node. The merged tree has 6 at that position.
3. if both the trees have null at a specific position, then the merged tree too will have null at that position.
NOTE: You need to create a new tree. You can not modify the original trees.
Example:
root1- 1 root2- 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
merged- 3
/ \
4 5
/ \ \
5 4 7
Solution:
We will use a recursive approach for this.
1. if both the nodes are null, we return null;
2. if one of them is null, we create newRoot with the value of the non-null node. Then we merge the left and right subtrees recursively;
3. if none of them is null, we create newRoot with a value equal to the sum of both nodes and then merge the left and right subtrees recursively.
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 && root2 == null) {
return null;
}
TreeNode newRoot;
if (root1 == null) {
newRoot = new TreeNode(root2.val);
newRoot.left = mergeTrees(null, root2.left);
newRoot.right = mergeTrees(null, root2.right);
} else if (root2 == null) {
newRoot = new TreeNode(root1.val);
newRoot.left = mergeTrees(root1.left, null);
newRoot.right = mergeTrees(root1.right, null);
} else {
newRoot = new TreeNode(root1.val + root2.val);
newRoot.left = mergeTrees(root1.left, root2.left);
newRoot.right = mergeTrees(root1.right, root2.right);
}
return newRoot;
}
}
Time complexity- O(max(number of nodes in both trees))
Space complexity- O(max(height of both trees))
The code can be improved by using the ternary operator.
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 && root2 == null) {
return null;
}
int val1 = root1 != null ? root1.val : 0;
int val2 = root2 != null ? root2.val : 0;
TreeNode newRoot = new TreeNode(val1 + val2);
newRoot.left = mergeTrees(root1 != null ? root1.left : null,
root2 != null ? root2.left : null);
newRoot.right = mergeTrees(root1 != null ? root1.right : null,
root2 != null ? root2.right : null);
return newRoot;
}
}
Written by S. Kumar on June 27th, 2021
3. How do you increase the skewed tree?
This interview question concentrates on using the Java binary search tree.
You are given the root node of a binary search tree. Your task is to rearrange the tree such that,
1. the root is the node with the smallest value, and
2. every node has no left child, only right child, and
3. every parent is smaller than their right child.
/*Example*/
Given tree
5
/ \
3 8
/ / \
2 6 9
/ \
1 7
Expected
1
2
3
4
5
6
7
8
9
Solution:
We know that in a BST (binary search tree), the inorder traversal returns nodes in increasing order. We will create a list of all the nodes in the tree in increasing order using inorder traversal.
After that, we will iterate over the list. and will set left of each node to null and set right of current node to the next node.
import java.util.*;
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 increasingBST(TreeNode root) {
ArrayList<TreeNode> inOrderTraversal = new
ArrayList<TreeNode>();
inOrder(root,inOrderTraversal);
// remove left child, if any
inOrderTraversal.get(0).left = null;
for (int i = 1; i < inOrderTraversal.size(); i++) {
inOrderTraversal.get(i - 1).right =
inOrderTraversal.get(i);
// remove left child, if any
inOrderTraversal.get(i).left = null;
}
return inOrderTraversal.get(0);
}
public void inOrder(TreeNode root, ArrayList<TreeNode>
inOrderTraversal) {
if (root == null) return;
inOrder(root.left, inOrderTraversal);
inOrderTraversal.add(root);
inOrder(root.right, inOrderTraversal);
}
}
n = number of nodes in both trees
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
4. Invert the binary tree.
This interview question concentrates on using Java binary tree inversion through iteration and recursion.
Given the root of a binary tree, invert the tree, and return its root.
For a tree to be inverted the left child of every node has to be swapped with the right child.
/*Example*/
4
/ \
2 7
/ \ / \
1 3 6 9
Inverting the above tree.
4
/ \
7 2
/ \ / \
9 6 3 1
Solution:
Let’s replicate the inverting process for the given sample tree:
Traverse through the tree and for every node, we swap its left subtree with the right subtree.
4
/ \
2 7
We are currently at node 4. We swap the left subtree (2) with the right subtree(7)
4
/ \
7 2
/ \ / \
6 9 1 3
We now invert the subtrees rooted at nodes 2 and 7.Repeat the same process for nodes 7 and 2. Note that we do not need to repeat this process for leaf nodes as they don’t have any left and right children.
4
/ \
7 2
/ \ / \
9 6 3 1
Approach I (Recursive):
We can solve the problem recursively. For each node, we first recursively invert the left and right subtrees. Then we swap the left and right subtree with each other.
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) return root;
TreeNode leftNode = invertTree(root.left);
TreeNode rightNode = invertTree(root.right);
root.right = leftNode;
root.left = rightNode;
return root;
}
}
Time complexity- O(n) where n is the number of nodes
Space complexity- O(h) where h is the height of the tree
Approach II (Iterative):
This approach is similar to a recursive one. We first swap the left and right children of the root. Now instead of recursively calling the invert function, we push both these nodes to a stack. This stack contains nodes whose children haven’t been swapped.
In each iteration, we pop one node from the stack. We swap its left and right children and add them to the stack if they exist. We repeat this process until all nodes are processed and their children are inverted.
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) return root;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
TreeNode leftNode = node.left;
node.left = node.right;
node.right = leftNode;
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return root;
}
}
Time complexity- O(n) where n is the number of nodes
Space complexity- O(n) where n is the number of nodes
Written by S. Kumar on June 27th, 2021
5. Are the two binary trees the same or not?
This interview question concentrates on using Java recursion and iteration.
Given the roots of two binary trees node1 and node2, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
/*Example 1*/
4
/ \
1 2
4
/ \
2 1
False, the left node of 4 is 1 in the first tree but is 2 in the next.
/*Example 2*/
5
/ \
7 8
/ \
4 2
5
/ \
7 8
/ \
4 2
True, All the values are the same and they are identical
Solution:
Approach I (Recursive):
For two trees to be identical. All the values must be the same and they should be structurally similar. That is if values exist at one tree they must also exist on the other and vice versa.
We will visit all the nodes of both the trees starting with the root nodes.
We compare the similarity of the root nodes. If they don’t have the same value we return false. Otherwise, we recursively check for the similarity of the right and left subtree.
Return true if all the conditions are met else return false.
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 isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
boolean isLeftTreeSame = isSameTree(p.left, q.left);
boolean isRightTreeSame = isSameTree(p.right, q.right);
boolean isSame = p.val == q.val && isLeftTreeSame &&
isRightTreeSame;
return isSame;
}
}
Time complexity- O(n) where n is the number of nodes in the tree
Space complexity- O(n)
Approach II (Iterative):
This approach is similar to a recursive one. We first check the similarity of the root nodes of both trees. Now instead of recursively calling the similarity function, we push both these nodes to a stack. This stack contains nodes whose children haven’t been checked for similarity.
In each iteration, we pop two nodes from the stack. We first check for their similarity and then check for the similarity of their left and right children. If both the children are similar we add them to the stack if they exist. We repeat this process until all nodes are processed.
In the end, we return the true else we return false during iteration if any of the conditions aren’t met.
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 isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(p);
stack.push(q);
while (!stack.empty()) {
TreeNode subnode2 = stack.pop();
TreeNode subnode1 = stack.pop();
System.out.println(subnode2.val + " " + subnode1.val);
//If the values of the nodes aren't equal
if (subnode2.val != subnode1.val) return false;
if (subnode1.left != null && subnode2.left != null) {
//If left subsubnode exists
stack.push(subnode1.left);
stack.push(subnode2.left);
} else if (subnode1.left != null ||
subnode2.left != null) {
//If one of the left subsubnode is null
return false;
}
if (subnode1.right != null && subnode2.right != null) {
//If right subsubnode exists
stack.push(subnode1.right);
stack.push(subnode2.right);
} else if (subnode1.right != null ||
subnode2.right != null) {
//If one of the right subsubnode is null
return false;
}
}
return true;
}
}
Time complexity- O(n) where n is the number of nodes in the tree
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
6. What is the maximum depth of the binary tree?
This interview question concentrates on using Java functions using recursion and iteration.
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.
/*Example*/
4
/ \
1 2
/ \
9 10
The depth of the tree is 3
Solution:
4
If only a single node was given to us we would have returned its depth as 1
4
/ \
1 2
The max depth of the above tree is 2. 1 root + 1 depth of child
4
/ \
1 2
/
9
The max depth of the above tree is 3. 4 -> 2 -> 9
Depth from the left node(1) is 2
Depth from the right node(2) is 3
You can notice that the max depth is the maximum depth out of the left and the right nodes of the root and adding 1 to it (root depth=1)
Hence maxDepth = max(leftNodeDepth,rightNodeDepth) + 1
Approach I (Recursive):
We visit all the nodes of the tree starting with the root node. For each node, we recursively check the max depth of the left subtree and the right subtree if they exist.
In the end we return one plus the max of the depth out of the left and right subtree.
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 maxDepth(TreeNode root) {
if (root == null) return 0;
int right = maxDepth(root.right);
int left = maxDepth(root.left);
return Math.max(left, right) + 1;
}
}
Time complexity- O(n) where n is the number of the nodes in the tree
Space complexity- O(h) where h is the height of the tree
Approach II (Iterative):
This approach is similar to a recursive one. We first check if the root node exists. Now instead of recursively calling the max depth function, we push this node to a stack. This stack contains nodes whose children haven’t been checked for similarity.
Our stack should only be filled with nodes that are of the same level thus we maintain a variable s that stores the size of our stack. In each iteration, we pop s nodes from the stack and increment our max depth variable. Then we push the left and right children to the stack if they exist.
We repeat this process until all nodes are processed.
In the end, we return the max depth variable.
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 maxDepth(TreeNode root) {
if (root == null) return 0;
int finalAns = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
finalAns++;
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return finalAns;
}
}
Time complexity- O(n) where n is the number of the nodes in the tree
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
7. Using in-order traversal of the binary tree, return an array.
This interview question focuses on the developer's skills with Java recursive and iterative methods.
You are given a binary tree. Perform inorder traversal of the tree and return the result in the form of an array.
/*Example*/
Given tree:
1
/ \
2 3
/ / \
4 5 6
Expected output: [4, 2, 1, 5, 3, 6]
Solution:
Approach I (recursive):
We will make a helper function _inorderTraversal which also takes the result array. This function will, first, call on the left child recursively. Then it adds the value of the current node to the result array, and then recurs on the right child.
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 List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
_inorderTraversal(root, result);
return result;
}
void _inorderTraversal(TreeNode node, List<Integer> result) {
if (node == null) return;
_inorderTraversal(node.left, result);
result.add(node.val);
_inorderTraversal(node.right, result);
}
}
n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Approach II (iterative):
We will have two arrays: result and stack. The result array will be our final answer array. The stack array stores the nodes which need to be processed yet. For a given node, we first go to the deepest leftmost child. For example:-
1
/ \
2 3
/ / \
4 5 6
For node 1, the deepest leftmost child is 4
For node 3, the deepest leftmost child is 5
Then, we pop a node from the stack and push its value to the result. Then we iterate over the right child of the popped 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 List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr != null || stack.size() != 0) {
// find deepest leftmost child
// add push intermediate nodes
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
// we have reached the leftmost child
curr = stack.pop();
result.add(curr.val);
// now iterate its right subtree
curr = curr.right;
}
return result;
}
}
n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Written by S. Kumar on June 27th, 2021
8. What is the lowest common ancestor in a binary search tree?
This question shows the developer's skills working with Java loops.
You are given the root node of a binary search tree. You are also given nodes node1 and node2. Your task is to find and return the lowest common ancestor (LCA) of node1 and node2 in the given tree.
/*Example*/
Given tree:
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
Given node1 = 0, node2 = 5
Expected output: 2
Explanation: common ancestors of 0 and 5 are 2 and 6 out of which 2 is the lowest common ancestor.
LCA of 0 and 2 is 2
LCA of 2 and 3 is 2
LCA of 5 and 6 is 6
LCA of 3 and 5 is 4
LCA of 7 and 4 is 6
Solution:
First, we need to make some observations. There are three cases for positions of the two nodes.
CASE I:- when both are in the left subtree of some node
x1
/ \
node1 x
\
node2 Here LCA is node1
CASE II:- when both are in the right subtree of some node
x1
/ \
x node1
\
node2 Here LCA is node1
CASE III:- when both nodes are in different subtrees of a node
x1
/ \
node1 x
/
node2 Here LCA is x1
Since the given tree, it is easier to find in which case node1 and node2 lie with respect to a given node. We will traverse the BST starting from the root node of the tree recursively. During recursion, for a given node root:
1. if the values of both node1 and node2 less than the value of root, then node1 and node2 both lie on the left subtree of root;
2. if the values of both node1 and node2 greater than the value of root, then node1 and node2 both lie on the right subtree of root;
3. otherwise there is a split at the root node, thus the root node will be their LCA.
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 lowestCommonAncestor(TreeNode root, TreeNode p,
TreeNode q) {
int rootValue = root.val;
int value1 = p.val;
int value2 = q.val;
if (value1 > rootValue && value2 > rootValue) {
// both are in right subtree
return lowestCommonAncestor(root.right, p, q);
} else if (value1 < rootValue && value2 < rootValue) {
// both are in left subtree
return lowestCommonAncestor(root.left, p, q);
} else {
return root;
}
}
}
n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Written by S. Kumar on June 27th, 2021
9. Can you find the zigzag level order traversal of the node values?
This interview question concentrates on the developer's ability to work with or without Java reversal.
You are given the root node of a binary tree. Your task is to return the zigzag level order traversal of its nodes' values. That zigzag level order traversal is first level from left to right (LTR), next from right to left (RTL) and so on.
/*Example*/
Given tree:
3
/ \
9 2
/ \
4 5
Expected output: [[3], [2, 9], [4, 5]]
Explanation:
First level: [3] from left to right
Second level: [9, 2] => [2, 9] from right to left
Third level: [4, 5] from left to right
Solution:
Approach I (using reverse):
This is the easiest approach. We will find the level order of the tree and will reverse every other level order. previousLevel stores the nodes in level order of the previous level. Then we find the level order of the current level in currLevel. To find this, we will iterate over each node in previousLevel and push their left and right children to currLevel. After doing so, we will find the values of the current level in currLevelValues by converting currLevel list to stream and using Stream.map method and converting it back to list. If the current is supposed to be right to left (RTL), we reverse the values of currLevelValues using Collections.reverse method. Then we store the values of the current level in the desired order to the result array. Then we proceed to the next level.
If the currLevel is empty, it means previousLevel was the last level in the binary tree. In this case we break the loop.
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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
result.add(Arrays.asList(root.val));
List<TreeNode> previousLevel = Arrays.asList(root);
boolean leftToRight = false;
while(true) {
List<TreeNode> currLevel = new ArrayList<TreeNode>();
for (TreeNode node : previousLevel) {
if (node.left != null) currLevel.add(node.left);
if (node.right != null) currLevel.add(node.right);
}
List<Integer>currLevelValues = currLevel
.stream()
.map(v -> v.val)
.collect(Collectors.toList());
if (currLevel.size() == 0) break;
if (!leftToRight) Collections.reverse(currLevelValues);
result.add(currLevelValues);
previousLevel = currLevel;
leftToRight = !leftToRight;
}
return result;
}
}
n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Approach II (without using reverse):
Reversing the array is less efficient. We can use stacks for the reverse effect. In this approach, we will have a stack (array in JavaScript) currentLevel which stores the nodes of the current level which we are traversing and pushing values. In each iteration, we retrieve the last node in currentLevel using Java.util.Stack.pop() method. The variable leftToRight stores the direction of the next level. If it is true, it means the next level is supposed to be LTR direction and vice-versa. If the next level is supposed to be in the LTR direction, we push the right child first then the left child, because while retrieving the node stack, the left child will come first which will be the correct order. And if the next level is supposed to be in the RTL direction, we push the left child first then the right child.
When the currentLevel is traversed, we
1. push its values to the result array,
2. reverse the direction of leftToRight
3. mark nextLevel to be currentLevel
4. and initialize new arrays for currLevelValues and nextLevel.
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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
List<Integer> currLevelValues = new ArrayList<Integer>();
Stack<TreeNode> currentLevel = new Stack<TreeNode>();
currentLevel.push(root);
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
boolean leftToRight = false;
while (!currentLevel.empty()) {
TreeNode node = currentLevel.pop();
TreeNode left = node.left;
TreeNode right = node.right;
currLevelValues.add(node.val);
if (leftToRight) {
if (right != null) nextLevel.push(right);
if (left != null) nextLevel.push(left);
} else {
if (left != null) nextLevel.push(left);
if (right != null) nextLevel.push(right);
}
// finished current level
if (currentLevel.empty()) {
result.add(new ArrayList<Integer>(currLevelValues));
leftToRight = !leftToRight;
currLevelValues = new ArrayList<Integer>();
currentLevel = nextLevel;
nextLevel = new Stack<TreeNode>();
}
}
return result;
}
}
n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
10. How do you delete the key from the BST and return the modified tree root node?
This question shows the developer's ability to work with Java recursion and iteration.
You are given the root node of a binary search tree (BST). Each node contains an integer value. You are also given an integer key. Your task is to delete the key from the given BST and return the root node of the modified tree.
/*Example*/
Given key = 3 and tree:
5
/ \
3 6
/ \ \
2 4 7
Expected output:
5
/ \
4 6
/ \
2 7
The following result is also accepted
5
/ \
2 6
\ \
4 7
Solution:
Approach I (recursive):
In the recursive approach, we will compare the value of the current node with the key.
â— If the key is lesser, we will delete it in the left subtree;
â— if the key is greater, we will delete it in the right subtree.
If the key is equal to the value of the current node. We will delete this node. If this node does not have a left child, we will directly return its right child (this will make the desired node deleted). The same is true when it has only the left child, then we return the left child. If this node has both children, then we do a different procedure. First, we will find the node with the minimum value in the right subtree (say it is minNode). Then we copy the value of the minNode to the node to be deleted. Then we delete minNode in the right subtree. In the following tree, (7) is the node with a minimum value in the right subtree of (5).
5 <--- (node to be deleted)
/ \
3 10
/ \
8 11
/ \
(minNode)-> 7 9
After copying the value of minNode (7) to the node to be deleted (5). Note that it doesn’t break the property of BST.
7 <--- (node to be deleted)
/ \
3 10
/ \
8 11
/ \
(minNode)-> 7 9
After deleting the minNode:
7
/ \
3 10
/ \
8 11
\
9
We find the minNode using the function findMinimum.
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 deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
return root;
}
// we are here means root has value equal `key`
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode minNode = findMinimum(root.right);
// copy value
root.val = minNode.val;
// now delete the minnode the right subtree
root.right = deleteNode(root.right, root.val);
return root;
}
private TreeNode findMinimum(TreeNode node) {
while(node.left != null) {
node = node.left;
}
return node;
}
}
n = number of nodes in the tree
Time complexity- O(n) // in case of skewed tree
Space complexity- O(n) // for recursion in case of skewed tree
Approach II (iterative):
In this approach, we solve the problem using an iterative approach. We also delete the node actually instead of copying the value. We create two additional helper functions:
1. findMinimum:- This function finds the minNode in the right subtree of the given node and returns an array containing the parent of minNode and the minNode itself.
2. deleteRootNode:- This function always deletes the root node of the passed tree and returns the modified tree.
In our main function deleteKey, we iterate over the node. We pinpoint the node to be deleted using the same condition in the previous approach:
â— If the key is lesser, we will delete it in the left subtree,
â— if the key is greater, we will delete it in the right subtree.
But this time, we do it iteratively. We have two variables: curr and parent. After the loop ends, curr will be the node to be deleted, and parent will be the parent of curr (the node to be deleted). If a parent is null, it means the root of the tree has a value equal to the key. In this case, we will directly call deleteRootNode and return it. Otherwise, we check two conditions:
â— If curr is the left child of the parent, we call deleteRootNode with parent.left (or curr) and overwrite parent.left (we are asking deleteRootNode to delete the root node of the tree passed as an argument, that is, parent.left, that is, delete parent.left and return the modified tree).
â— And if curr is the right child of the parent, we call deleteRootNode with parent.right (or curr) and overwrite parent.right
â— In the end, we return root.
Now let’s see how deleteRootNode works. In this function, we always need to delete the root node. If the root has only one child, we directly return that child. Otherwise, we do a different procedure. First, we find the node with the minimum value in the right subtree of root using findMinimum function. We also find its parent. Let these be minNode and parentOfMinNode. The minNode will not have a left child (if it were so, that left child would have been the minNode. see the previous approach for example). Let us take the following example
5 <--- (node to be deleted aka root)
/ \
3 10 <- (parentOfMinNode)
/ \
(minNode)-> 8 11
\
9
We perform the following steps:
1. Since we are to delete the root, we assign its left-child to be the left child of minNode. The tree becomes:-
5 <--- (node to be deleted aka root)
/ \
3 10 <- (parentOfMinNode)
/ \
(minNode)-> 8 11
/ \
3 9
^ (the left sub-tree of the root is the left subtree of minNode)
----------------------------------------------------------------------
2. The minNode will take the place of the root. So we have to take care of the left and right children of the root. We have taken care of the left child of root in the previous step. Now we need to assign the right child of root to the right child of minNode. But minNode already has its right child. To do this, we first take care of the right child of minNode. Since the left child of parentOfMinNode will be overwritten, we assign the right of minNode to the left of parentOfMinNode. Then, we assign the right child of root to the right child of minNode. The tree becomes:-
(minNode)-> 8 5 (root is now orphan node)
/ \
3 10 <- (parentOfMinNode)
/ \
9 11
(the right ^^^^^ subtree of minNode is the left subtree of parentOfMinNode)
----------------------------------------------------------------------
3. Then we return minNode effectively deleting the desired 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 deleteNode(TreeNode root, int key) {
TreeNode curr = root;
TreeNode parent = null;
while (curr != null && curr.val != key) {
parent = curr;
if (key < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
// the root node of the given BST
// has value equal to `key`
if (parent == null) {
return deleteRootNode(root);
}
// the node to be deleted is the left child of `parent`
if (parent.left == curr) {
parent.left = deleteRootNode(parent.left);
}
// the node to be deleted is the right child of `parent`
if (parent.right == curr) {
parent.right = deleteRootNode(parent.right);
}
return root;
}
private TreeNode deleteRootNode(TreeNode root) {
if (root == null) return null;
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = findMinimum(root.right).getValue();
TreeNode parentOfMinNode = findMinimum(root.right).getKey();
minNode.left = root.left;
if (root.right != minNode) {
parentOfMinNode.left = minNode.right;
minNode.right = root.right;
}
return minNode;
}
private Pair<TreeNode, TreeNode> findMinimum(TreeNode node) {
TreeNode parent = null;
while(node.left != null) {
parent = node;
node = node.left;
}
return new Pair(parent, node);
}
}
n = number of nodes in the tree
Time complexity- O(n) // in case of skewed tree
Space complexity- O(1)
Advantages:
1. Recursion stack is avoided giving constant time complexity
2. It does not copy values from nodes which we did in the recursive approach. In reality, the node does not contain only integer values. Copying the data in nodes can be a time-consuming task.
Written by S. Kumar on June 27th, 2021
11. Return all elements in two binary search trees.
This question shows the developer's ability to work with Java binary search and indices.
You are given the root nodes root1 and root2 of two binary search trees (BST). Your task is to return all the integers from both trees in an array in ascending order.
/*Example*/
Given trees:
2 1
/ \ / \
1 4 0 3
Expected output: [0, 1, 1, 2, 3, 4]
Solution:
First of all, we find all the nodes in each tree into tree1 and tree2. Since both are binary search trees, we will do inorder over the trees and the resulting array will be already sorted. Next, we will combine both arrays into one sorted array. We will have two pointers (indices) i and j pointing to the arrays tree1 and tree2 respectively. We will have a third pointer k, pointing to the next location in res array where the next larger element will be stored. We will iterate over both the arrays tree1 and tree2, find the next larger element and store it in res array. At last, we return res.
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 {
private List<Integer> res;
public List<Integer> getAllElements(TreeNode root1,
TreeNode root2) {
List<Integer> tree1 = inorderTraversal(root1);
List<Integer> tree2 = inorderTraversal(root2);
int tree1Count = tree1.size();
int tree2Count = tree2.size();
Integer res[] = new Integer[tree1Count + tree2Count];
int i = 0;
int j = 0;
int k = 0;
while (i < tree1Count && j < tree2Count) {
res[k++] = tree1.get(i) < tree2.get(j)
? tree1.get(i++)
: tree2.get(j++);
}
while(i < tree1Count) {
res[k++] = tree1.get(i++);
}
while(j < tree2Count) {
res[k++] = tree2.get(j++);
}
return Arrays.asList(res);
}
private List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<Integer>();
inorder(root);
return res;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
res.add(node.val);
inorder(node.right);
}
}
n = number of nodes in tree1
m = number of nodes in tree2
Time complexity- O(n + m)
Space complexity- O(n + m)
Written by S. Kumar on June 27th, 2021
12. How do you prune the binary tree?
This question shows the developer's ability to work with Java recursion.
You are given the root node of a binary tree. A node of the tree has a value equal to either 0 or 1. Your task is to remove those subtrees from the tree which have no node with a value equal to 1.
/*Example*/
Given tree:
1
\
0
/ \
0 1
Expected tree:
1
\
0
\
1
Given tree:
1
/ \
0 1
/ \ / \
0 0 0 1
Expected tree:
1
\
1
\
1
Solution:
We will remove the nodes recursively. We will do the depth-first search over the whole tree. If the current node is a leaf tree and it has a value equal to 0, we will remove it. To remove a node, we return null to the parent node. If we don’t need to remove the node, we return the node itself.
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 pruneTree(TreeNode root) {
if (root == null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
boolean isLeaf = root.left == null && root.right == null;
if (isLeaf && root.val == 0) {
return null;
}
return root;
}
}
n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
13. Create a maximum binary tree.
This question focuses on Java elements and recursion.
You are given an integer array nums with no duplicates. Your task is to create a maximum binary tree using:
1. Create a root node with max value in nums
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value
3. Recursively build the right subtree on the subarray prefix to the right of the maximum value
/*Example*/
Given nums = [3, 2, 1, 6, 0, 5]
Expected tree:
6
/ \
3 5
\ /
2 0
\
1
Solution:
We will do this recursively. We will create a helper function construct that constructs the maximum binary tree on nums between indices left and right. Thus our required tree will be formed by construct(nums, 0, nums.length - 1). This function finds the index of the maximum element in the subarray using another helper function findMaxIndex. Then create a node with that maximum value and recursively build the left and right subtrees.
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 constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length - 1);
}
private TreeNode construct(int[] nums, int left, int right) {
if (left > right) return null;
int maxIndex = findMaxIndex(nums, left, right);
TreeNode node = new TreeNode(nums[maxIndex]);
node.left = construct(nums, left, maxIndex - 1);
node.right = construct(nums, maxIndex + 1, right);
return node;
}
private int findMaxIndex(int[] nums, int left, int right) {
int maxIndex = left;
for (int i = left; i <= right; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
}
n = length of nums
Time complexity- O(n2)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
14. Distribute coins in the binary tree.
This question focuses on Java traversal.
You are given the root node of a binary tree. The tree contains n nodes. For each node, node.val represents the number of coins that node has. The total number of coins in the tree is equal to the number of nodes, that is, equal to n.
You perform a series of operations on the tree. In one operation, you take one coin from a node and transfer it to one of its adjacent nodes (that is either from parent to child or from child to parent). Your task is to find the minimum number of operations such that each node has exactly one coin.
/*Example*/
1. Given tree:
3
/ \
0 0
Expected output: 2
Explanation: From the root node, we move one coin to the left child and one coin to the right child. Hence 2 operations.
2. Given tree:
0
/ \
3 0
Expected output: 3
Explanation: From the left child, we move two coins to the root node (total 2 operations, one for each coin). The resulting tree becomes:
2
/ \
1 0
Then we move one coin from the root node to the right child. So total 3 operations.
Solution:
We will do post-order traversal on the tree. For every node, we will calculate the balance factor. The balance factor for a node is the number of coins is the number of extra coins in its both subtree including the node itself. Consider the following tree, the balance factors are shown in parentheses:
 
0 (0)
/ \
(+1) 0 0 (0)
/ \ / \
(+3) 4 0 3(=2) 0 (-1)
(-1)
If a node has a positive balance factor, it means the node has extra coins it would like to give. If the balance factor is negative, it means the node needs that number of coins such that every node has exactly one coin. Let leftBalance and rightBalance be the balance factors of the left and right children of a node. This node will take/give leftBalance number of coins to/from the left child.
Thus the operationsCount while taking/giving to/from the left child will be increased by leftBalance. The same applies to the right child. The number of operations for a node that will transact coins with its children nodes will be equal to the sum of the absolute values of the balance factors of the children nodes.
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 {
private int operationsCount = 0;
public int distributeCoins(TreeNode root) {
traverse(root);
return operationsCount;
}
private int traverse(TreeNode root) {
if (root == null) return 0;
int leftBalance = traverse(root.left);
int rightBalance = traverse(root.right);
operationsCount +=
Math.abs(leftBalance) + Math.abs(rightBalance);
return root.val + leftBalance + rightBalance - 1;
}
}
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021