Interview Questions on Trees in Python

Minimal Tree

We’re given a sorted array(ascending order) with unique integer elements. Write an algorithm to create a binary search tree with minimal height.

For the implementation of the solution to the given problem, we need to initialize the binary search tree class and overwrite the __init__ function as per our requirements. The method takes in three parameters – the data of the binary search tree, the left variable for the left subtree, and the right variable for the right subtree.

#Initializing the Binary Search Tree class
class BSTNode:
    def __init__(self, data=None, left = None, right= None):
        self.data = data
        self.left = left
        self.right = right

The minimalTree method will be used to create a binary search tree of minimum height using the given sorted array. It takes the sorted array as parameter.

The minimalTree method is based on the following algorithm:

• Create function and input the sorted array as parameter.
• If the length of the sorted array is 0, return None.
• If the length of the sorted array is 1, return the sole element of the array as the root node of the binary search tree.
• Create a variable mid to store the value of the mid point of the array under consideration, i.e., mid = int(len(sortedArray)/2)
• Recursively invoke the minimalTree method to add the elements to the left of the mid point in the left subtree.
• Recursively invoke the minimalTree method to add the elements to the right of the mid point in the right subtree.
• Finally, return the Binary Search Tree with all the elements inserted.

#Function to create a binary search tree of minimum height
def minimalTree(sortedArray):
    if len(sortedArray) == 0:
        return None
    if len(sortedArray) == 1:
        return BSTNode(sortedArray[0])
    mid = int(len(sortedArray)/2)
    left = minimalTree(sortedArray[:mid])
    right = minimalTree(sortedArray[mid+1:])
    return BSTNode(sortedArray[mid], left, right)

sortedArray = [1,2,3,4,5,6,7,8,9]
bst = minimalTree(sortedArray)

The binary Search Tree of minimal height has been created. However, the given solution won’t display the elements of the tree. To print the elements of the output tree, we can use Level Order Traversal that we studied before in the article, Binary Search Tree in Python.

List of Depths

We’re given a binary search tree. Design an algorithm which creates a linked list of all the nodes at each depth. This means that if we have a binary search tree of depth D, then we’ll get D linked lists as output.

For the implementation of the solution to the given problem, we need to initialize the binary tree class and overwrite the __init__ function as per our requirements.

#Initializing the Binary Tree class
class BinaryTree:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Further, we initialize the linked list class and overwrite its __init__ function as well. Also, we include an add function to add nodes to the linked list and overwrite the __str__ function to display elements as desired.

#Initializing the Linked List class
class LinkedList:
    def __init__(self, val):
        self.val = val
        self.next = None
    
    def add(self, val):
        if self.next == None:
            self.next = LinkedList(val)
        else:
            self.next.add(val)
    def __str__(self):
        return "({val})".format(val = self.val) + str(self.next)

The depth method is used to return the depth of a given node. It takes this node as the parameter. If the left subtree of that node has a greater depth than the right subtree, we return that depth. Otherwise, the depth of the right subtree is returned.

#Initializing the depth class
def depth(tree):
    if tree == None:
        return 0
    if tree.left == None  and tree.right == None:
        return 1
    else:
        depthLeft = 1 + depth(tree.left)
        depthRight = 1 + depth(tree.right)
        if depthLeft > depthRight:
            return depthLeft
        else:
            return depthRight

The treeToLinkedList method is a recursive function used to convert each depth of a tree into a linked list. The function takes three parameters as inputs – a node of the tree, a custom dictionary variable, and a variable to store the depth of the node.

The custom dictionary is used to store the elements of a specific depth. The key part of this dictionary holds the depth of the tree and the values part holds all the nodes of the tree at that particular depth.

The treeToLinkedList method is based on the following algorithm

• Create function and input the root node of the tree as parameter
• If the depth of the node is None, set the depth to the depth of the curret node.
• If the custom dictionary has no values for the current key “depth”, simply add the value of this node to the linked list.
• Otherwise, add all nodes of that depth to the custom dictioary. If depth equals 1(i.e, the nodes are leaf nodes), retun the custom dictionary.
• Recursively invoke the treeToLinkedList method for the left subtree of each node.
• Recursively invoke the treeToLinkedList method for the right subtree of each node.
• Finally, return the custom dictionary at the end of the function.

#Function to create linked list for nodes at each depth of the tree
def treeToLinkedList(tree, custDict = {}, d = None):
    if d == None:
        d = depth(tree)
    if custDict.get(d) == None:
        custDict[d] = LinkedList(tree.val)
    else:
        custDict[d].add(tree.val)
        if d == 1:
            return custDict
    if tree.left != None:
        custDict = treeToLinkedList(tree.left, custDict, d-1)
    if tree.right != None:
        custDict = treeToLinkedList(tree.right, custDict, d-1)
    return custDict

mainTree = BinaryTree(1)
two = BinaryTree(2)
three = BinaryTree(3)
four = BinaryTree(4)
five = BinaryTree(5)
six = BinaryTree(6)
seven = BinaryTree(7)

mainTree.left = two
mainTree.right = three
two.left = four
two.right = five
three.left = six
three.right = seven

custDict = treeToLinkedList(mainTree)
print(custDict[3])
print(custDict[2])
print(custDict[1])

#Output
(1)None
(2)(3)None
(4)(5)(6)(7)None

Check Balanced

Implement a function to check if a binary tree is balanced. A balanced tree is defined to be a tree such that the heights of the two subtrees of any node differ by more than one.

For the implementation of the solution to the given problem, we need to initialize the Binary Tree class and overwrite the __init__ function as per our requirements. We do this by declaring the node class of the binary tree.

#Initializing the Binary Tree class
class Node():
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

The isBalanced function is given the root node of the tree as a parameter. This, in turn, calls the isBalancedHelper function which is responsible for returning a True output if the tree is balanced and False when it is not.

The isBalancedHelper function is based on the following algorithm:

• Declare the function and take the root of the tree as input.
• If the root node is None, return 0.
• Set a variable leftHeight. With this variable, invoke the function recursively for the left child of the current node. If leftHeight equals to -1, return -1.
• Set a variable rightHeight. With this variable, invoke the function recursively for the right child of the current node. If rightHeight equals to -1, return -1.
• If the absolute value of the difference between leftHeight and rightHeight is greater than 1, return -1.
• Return the following statement in the end of the algorithm: return max(leftHeight, rightHeight) + 1. If the max difference between any two subtrees is not greater than 1, a True value is returned.

#Function to check whether a given binary tree is balanced or not
def isBalancedHelper(root):
    if root is None:
        return 0
    leftHeight = isBalancedHelper(root.left)
    if leftHeight == -1:
        return -1
    rightHeight = isBalancedHelper(root.right)
    if rightHeight == -1:
        return -1
    if abs(leftHeight-rightHeight)>1:
        return -1
    
    return max(leftHeight, rightHeight) + 1

def isBalanced(root):
    return isBalancedHelper(root) > -1

N1 = Node("N1")
N2 = Node("N2")
N3 = Node("N3")
N4 = Node("N4")
N5 = Node("N5")
N6 = Node("N6")
N1.left = N2
N1.right = N3
N2.left = N4
N2.right = N5
N3.right = N6

print(isBalanced(N1))

#Output
True

Validate BST

Implement a function to check if a binary tree is a binary search tree.

A Binary Tree is a Binary Search Tree if:

• The left subtree of a node contains nodes with values lesser than that node.
• The right subtree of a node contains nodes with values greater than that node.
• These conditions apply on all the nodes of the tree.

For the implementation of the solution to the given problem, we need to initialize the Binary Tree class and overwrite the __init__ function as per our requirements. We do this by declaring the node class of the binary tree.

#Initializing the Binary Tree class
class Node():
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

The isBSTValid function is given the root node of the tree as a parameter. This, in turn, calls the isBSTHelper function which is responsible for returning a True output if the tree is Binary Search Tree and False when it is not.

The isBSTHelper function is based on the following algorithm:

• Declare the function and take the root of the tree as input, and two extra parameters – minValue and maxValue, initially set to infinity.
• If the root node is None, return True.
• Set a variable val and assign it the value of the current node. If the value is less than minValue or greater than maxValue, return False.
• Invoke the function recursively for the right child of the current node. If it fails, return False.
• Invoke the function recursively for the left child of the current node. If it fails, return False.
• Return True at the end of the function. This implies that all the nodes have been checked and thus the given tree is a binary search tree.

#Function to check whether a given binary tree is binary search tree or not
def BSTHelper(node, minValue = float('-inf'), maxValue = float('inf')):
    if not node:
        return True
    val = node.val
    if val <= minValue or val >= maxValue:
        return False
    if not BSTHelper(node.right, val, maxValue):
        return False
    if not BSTHelper(node.left, minValue, val):
        return False
    
    return True

def isBSTValid(root):
    return BSTHelper(root)

root1 = Node(2)
root1.left = Node(1)
root1.right = Node(4)

print(isBSTValid(root1))

root2 = Node(4)
root2.left = Node(1)
root2.right = Node(3)

print(isBSTValid(root2))

#Output
True
False

In-order Successor in BST

We are given a binary search tree. Write an algorithm to find the next node (i.e., the in-order successor) of a given node in the tree.

In a binary search tree, the in-order successor of a given node can be found in the mentioned two ways:

• If the right subtree of the node exists, then the successor lies in the right subtree.
• If the right subtree of the node does not exist, then the successor is one of the ancestors of the node.

For the implementation of the solution to the given problem, we need to initialize the Binary Tree class and overwrite the __init__ function as per our requirements. We do this by declaring the node class of the binary tree. Then, we define the insertNode class to input value in the tree.

#Initializing the Binary Tree class
class Node: 
	def __init__(self, key): 
		self.data = key 
		self.left = None
		self.right = None

def insertNode(node, data):
   if node is None:
       return Node(data)
   else:
       if data <= node.data:
           temp = insertNode(node.left, data)
           node.left = temp
           temp.parent = node
       else:
           temp = insertNode(node.right, data)
           node.right = temp
           temp.parent = node      
       return node

The minValue function is used to find the minimum value in a subtree. This is accomplished by traversing to the leftmost leaf element of the binary search tree. The inOrderSuccessor function takes two parameters – the root node of the binary search tree and the node whose in-order successor is to be found.

InOrder Traversal – 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90 -> 100

The inOrderSuccessor function is based on the following algorithm:

• Declare the function and take the root of the tree and a temporary current node as input.
• Let n be the node whose in-order successor is to be found.
• If the right child of n exists, return its value as the in-order successor.
• Otherwise, iterate over the tree and find the first ancestor for which n doesn’t lie in the right subtree. Return its value as the in-order successor.

#Function to return the in-order successor of a given node
def minValue(node):
    current = node
    while (current is not None):
        if current.left is None:
            break
        current = current.left
    return current

def inOrderSuccessor(root, n):
    if n.right is not None:
        return minValue(n.right)
    
    p = n.parent
    while p is not None:
        if n != p.right:
            break
        n = p
        p = p.parent
    return p 

root = None
root = insertNode(root, 4)
root = insertNode(root, 2)
root = insertNode(root, 8)
root = insertNode(root, 1)
root = insertNode(root, 3)
root = insertNode(root, 5)
root = insertNode(root, 9)

temp = root.left 
successor = inOrderSuccessor(root, temp)

if successor is not None:
    print("Inorder successor of %d is %d" %(temp.data, successor.data))
else:
    print("Inorder successor does not exist")

#Output
Inorder successor of 2 is 3

First Common Ancestor

We are given a binary tree. Write an algorithm to find the first common ancestor between two given nodes of the tree. Avoid storing additional nodes in any data structure

An ancestor of a node is any other node on the path from the node to the root

For the implementation of the solution to the given problem, we need to initialize the Binary Tree class and overwrite the __init__ function as per our requirements. We do this by declaring the node class of the binary tree.

#Initializing the Binary Tree class
class Node():
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Firstly, we create a helper function called findNodeInTree which takes in two parameters – the target node and the root node of the tree. This function returns True if the node is found and False if not.

#Helper function to find a target element
def findNodeInTree(target, rootNode):
    if not rootNode:
        return False
    if target == rootNode:
        return True
    else:
         return (findNodeInTree(target, rootNode.left) or findNodeInTree(target, rootNode.right))

Further, we define the findFirstCommonAncestor function which takes in three parameters – the two nodes under consideration and the root node of the tree. It is used to find the first common ancestor between two given nodes.

The findFirstCommonAncestor function is based on the following algorithm:

• Create the function and input the two nodes and the root node as parameter.
• Store the values of the findNodeInTree function for the nodes in the left subtree of the root. Name the variables n1OnLeft and n2OnLeft respectively.
• if the “exclusive or” of n1OnLeft and n2OnLeft is True(n1OnLeft ^ n2OnLeft), return the root node.
• Otherwise, recursively call the function for the right and left subtrees of the remaining nodes.

#Function to find the first common ancestor between two nodes
def findFirstCommonAncestor(n1, n2, root):
    n1OnLeft = findNodeInTree(n1, root.left)
    n2OnLeft = findNodeInTree(n2, root.left)

    if n1OnLeft ^ n2OnLeft:
        return root
    else:
        if n1OnLeft:
            return findFirstCommonAncestor(n1, n2, root.left)
        else:
            return findFirstCommonAncestor(n1, n2, root.right)

node54 = Node(54)
node88 = Node(88, node54)
node35 = Node(35)
node22 = Node(22, node35, node88)
node33 = Node(33)
node90 = Node(90, None, node33)
node95 = Node(95)
node99 = Node(99, node90, node95)
node44 = Node(44, node22, node99)
node77 = Node(77)
rootNode = Node(55, node44, node77)

commonAncestor = findFirstCommonAncestor(node88, node33, rootNode)
print(commonAncestor.value)

#Output 
44