### 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
```