8 Python Intermediate Level Tree Interview Questions & Answers
Below is a list of our Python 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 Python recursive and iterative functions.
You are given a binary tree. You have to check if the tree is symmetric about its centre.
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 centre. 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,
their value must be equal,
the left subtree of the first node must be the mirror of the right subtree of the second node,
the right subtree of the first node must be the mirror of the left subtree of the second node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isMirror(root1, root2):
‘’’
returns True if both root1 and root2 are mirrors of each other
‘’’
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
isLeftMirror = isMirror(root1.left, root2.right)
isRightMirror = isMirror(root1.right, root2.left)
return isLeftMirror and isRightMirror
def isTreeSymmetric(root):
‘’’
Input: (TreeNode) root of tree
Output: (TreeNode) root of reversed tree
‘’’
if not root:
return True
return isMirror(root.left, root.right)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 straight away 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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def isTreeSymmetric(root):
if not root:
return True
stack = []
stack.append(root.left)
stack.append(root.right)
while stack:
node1 = stack.pop()
node2 = stack.pop()
if not node1 and not node2:
continue
if not node1 or not node2:
return False
if node1.val != node2.val:
return False
stack.append(node1.left)
stack.append(node2.right)
stack.append(node1.right)
stack.append(node2.left)
return TrueTime 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 Python functions.
You are given root nodes root1 and root2 of two binary trees. Your task is to merge them to form a new binary tree. The merge rules are as follows-
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
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.
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 7Solution:
We will use a recursive approach for this.
if both the nodes are null, we return null;
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;
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mergeTrees(root1, root2):
if not root1 and not root2:
return None
if not root1:
return root2
if not root2:
return root1
root = TreeNode(root1.val + root2.val)
root.left = mergeTrees(root1.left, root2.left)
root.right = mergeTrees(root1.right, root2.right)
return rootTime complexity- O(max(number of nodes in both trees))
Space complexity- O(max(height of both trees))
Written by S. Kumar on June 27th, 2021
3. How do you increase the skewed tree?
This interview question concentrates on using the Python binary search tree.
You are given the root node of a binary search tree. Your task is to rearrange the tree such that,
the root is the node with the smallest value, and
every node has no left child, only right child, and
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
9Solution:
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 the left of each node to null and set the right of the current node to the next node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inOrder(root, nodes):
if not root:
return
# traverse left sub tree
inOrder(root.left, nodes)
# current node
nodes.append(root)
# right node
inOrder(root.right, nodes)
return nodes
def toRightSkewedBst(root):
# get all the nodes in BST in sorted order
# using Inorder traversal
nodes = inOrder(root, [])
# create an empty tree
curr = skewTree = TreeNode()
# for each node remove its previous reference
# and make a skew tree
for node in nodes:
node.left = None
curr.right = node
curr = curr.right
return skewTree.rightn = 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 Python 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 1Solution:
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
if not root:
return None
left = invertTree(root.left)
right = invertTree(root.right)
root.left = right
root.right = left
return rootTime 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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(self, root):
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
# swap the children of node
node.left, node.right = node.right, node.left
# pass the children of current node into stack
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return rootTime 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 Python 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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def sameTree(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
left = sameTree(root1.left, root2.left)
right = sameTree(root1.right, root2.right)
return left and right
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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def areSameTree(p, q):
stack = [p, q]
while stack:
node1, node2 = stack.pop(), stack.pop()
if not node1 and not node2:
continue
if not node1 or not node2:
return False
if node1.val != node2.val:
return False
stack.append(node1.left)
stack.append(node2.left)
stack.append(node1.right)
stack.append(node2.right)
return TrueTime 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 Python 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 3Solution:
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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
# get height of left subtree
left = height(root.left)
# get height of right subtree
right = height(root.right)
return 1 + max(left, right)Time complexity- O(n) where n is the number of the 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 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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(self, root):
if not root:
return 0
height = 0
stack = [root]
while stack:
height += 1
temp = []
for node in stack:
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
stack = temp
return heightTime complexity- O(n) where n is the number of the nodes
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 Python methods.
You are given a binary tree. Perform in order 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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def _inorderTraversal(root: TreeNode, result: TreeNode) -> TreeNode:
if not root:
return
_inorderTraversal(root.left, result)
result.append(root.val)
_inorderTraversal(root.right, result)
return result
def inorderTraversal(root: TreeNode) -> List[int]:
return _inorderTraversal(root, [])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 resulting 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.
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> TreeNode:
result = []
stack = []
curr = root
while curr or stack:
# find deepest leftmost child
# add push intermediate nodes
while curr:
stack.append(curr)
curr = curr.left
# we have reached the leftmost child
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return resultn = 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 Python 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 6Solution:
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,
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;
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;
otherwise, there is a split at the root node, thus the root node will be their LCA.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root: TreeNode, node1: TreeNode, node2: TreeNode) -> TreeNode:
rootValue = root.val
value1 = node1.val
value2 = node2.val
if rootValue > value1 and rootValue > value2:
# both value lies to left of root
return lowestCommonAncestor(root.left, node1, node2)
elif rootValue < value1 and rootValue < value2:
# both value lies to right
return lowestCommonAncestor(root.right, node1, node2)
else:
# both values lies to different side
return rootn = 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