You need to login before you can make any post submission.
It is a node-based binary tree data structure which has the following properties:
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, key):
if(root is None):
root = Node(key)
# If key is lesser than root.val insert key in left subtree
if(key <= root.val):
if(root.left is None):
root.left = Node(key)
else:
insert(root.left, key)
# If key is greater than root.val insert key in right subtree
else:
if(root.right is None):
root.right = Node(key)
else:
insert(root.right, key)
def search(root, key):
# If root is None, then key doesn't exist.
if root is None:
return False
# If root's val matches the key, then we have found the key in
if(root.val == key):
return True
# If key is lesser than root's val search in left subtree else serach in right subtree.
if(key < root.val):
return search(root.left, key)
else:
return search(root.right, key)
def print_bst_inorder(root):
if(root):
print_bst_inorder(root.left)
print(root.val, end=" ")
print_bst_inorder(root.right)
print("Inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 into BST")
root = Node(8)
insert(root, 3)
insert(root, 10)
insert(root, 1)
insert(root, 6)
insert(root, 14)
insert(root, 4)
insert(root, 7)
insert(root, 13)
print("BST Now:")
print_bst_inorder(root)
print("\n")
print("Searching if 5 is present ? : {}".format(search(root, 5)))
print("Searching if 6 is present ? : {}".format(search(root, 6)))
Output:
When we delete a node, three possibilities arise.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def delete(root, key):
# Check if root None: key doesn't exist, not possible to delete.
if root is None:
return root
# If key is lesser than root.val: Delete the key in left subtree.
if(key < root.val):
root.left = delete(root.left, key)
# If key is greater than root.val: Delete the key in right subtree.
elif(key > root.val):
root.right = delete(root.right, key)
# If key is equal to root.val: Need to delete this root node.
else:
# If no child exists: make root None and return None.
if(root.left is None and root.right is None):
root = None
return None
# If left child exists: make root None and return left child.
elif(root.right is None):
temp = root.left
root = None
return temp
# If right child exists: make root None and return the right child.
elif(root.left is None):
temp = root.right
root = None
return temp
# If both child exists:
else:
# Get the min_node from right child subtree.
temp = min_node(root.right)
# Set the val of root as the val of min node.
root.val = temp.val
# Delete the min node from right subtree.
root.right = delete(root.right, temp.val)
# Finally return the root.
return root
def min_node(current_node):
# If current_node is None, min_node not possible
if(current_node is None):
return None
min_node = current_node
while(min_node.left):
min_node = min_node.left
return min_node
def insert(root, key):
if(root is None):
root = Node(key)
# If key is lesser than root.val insert key in left subtree
if(key <= root.val):
if(root.left is None):
root.left = Node(key)
else:
insert(root.left, key)
# If key is greater than root.val insert key in right subtree
else:
if(root.right is None):
root.right = Node(key)
else:
insert(root.right, key)
def print_bst_inorder(root):
if(root):
print_bst_inorder(root.left)
print(root.val, end=" ")
print_bst_inorder(root.right)
print("Insert:- 50, 30, 70, 20, 40, 60, 80 into BST.")
root = Node(50)
insert(root, 30)
insert(root, 70)
insert(root, 20)
insert(root, 40)
insert(root, 60)
insert(root, 80)
print("BST at start:")
print_bst_inorder(root)
print("\n")
delete(root, 20)
print("BST after deleting 20:")
print_bst_inorder(root)
print()
delete(root, 30)
print("BST after deleting 30:")
print_bst_inorder(root)
print()
delete(root, 50)
print("BST after deleting 50:")
print_bst_inorder(root)
print()
Output:
Given a binary tree check if it is a binary search tree.
For each node, check if left node is smaller and right node is greater.
import sys
INT_MIN = -sys.maxsize-1
INT_MAX = sys.maxsize
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_bst(root):
return (is_bst_util(root, INT_MIN, INT_MAX))
def is_bst_util(root, min_val, max_val):
# An empty tree is BST
if root is None:
return True
# If current root's val is either less than min_val allowed or greater than max_val allowed return False.
if root.val < min_val or root.val > max_val:
return False
# Check the subtrees recursively tightening the min or max constraint
return (is_bst_util(root.left, min_val, root.val-1) and is_bst_util(root.right, root.val+1, max_val))
def print_tree(root):
if(root):
print_tree(root.left)
print(root.val, end=" ")
print_tree(root.right)
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)
print("Binary Tree:")
print_tree(root)
print()
print("Is this binary Tree a BST ? : {}".format(is_bst(root)))
root = Node(3)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(4)
print("\nAnother Binary Tree:")
print_tree(root)
print()
print("Is this binary Tree a BST ? : {}".format(is_bst(root)))
Output:
Given values of two values n1 and n2 in a Binary Search Tree, find the Lowest Common Ancestor (LCA).
We may assume that both the values exist in the tree.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def lowest_common_ancestor(root, key1, key2):
while(root):
# If both key1 and key2 is smaller than root's val, then lca exist in left subtree.
if(key1 < root.val and key2 < root.val):
root = root.left
# If both key1 and key2 is greater than root's val, then lca exist in right subtree.
elif(key1 > root.val and key2 > root.val):
root = root.right
# Else this root is LCA.
else:
break
return root.val
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print("Lowest Common Ancestor of 10 and 14 is : {}".format(lowest_common_ancestor(root, 10, 14)))
print("Lowest Common Ancestor of 14 and 8 is : {}".format(lowest_common_ancestor(root, 14, 8)))
print("Lowest Common Ancestor of 10 and 22 is : {}".format(lowest_common_ancestor(root, 10, 22)))
Output:
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.
Get the given node by search using key.
If given_node’s right exist, simply return the min_node from right.
Else: Set successor as None and start from root and search for successor by travelling down the tree.
given_node हमेशा successor के left subtree में होना चाहिए, इसलिए successor तभी update करेंगे जब left subtree में जाएंगे ।
Finally return the successor.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorder_successor(root, key):
# Get the given node by search using key.
given_node = search(root, key)
# If given_node's right exist, simply return the min_node from right.
if(given_node.right):
return min_node(given_node.right)
# Set successor as None and start from root and search for successor by travelling down the tree.
successor = None
while(root):
# If given_node’s data < root’s data then go left side and update the successor.
# given_node हमेशा successor के left subtree में होना चाहिए,
# इसलिए successor तभी update करेंगे जब left subtree में जाएंगे ।
if(given_node.val < root.val):
successor = root
root = root.left
# Else if a given_node’s data > root’s data then go to right side.
elif (given_node.val > root.val):
root = root.right
# Else break when given_node’s data and root’s data are equal, given_node is found.
else:
break
# Finally return the successor.
return successor
def search(root, key):
# If root is None, then key doesn't exist.
if root is None:
return root
# If root's val matches the key, then we have found the key in
if(root.val == key):
return root
# If key is lesser than root's val search in left subtree else serach in right subtree.
if(key < root.val):
return search(root.left, key)
else:
return search(root.right, key)
def min_node(current_node):
# If current_node is None, min_node not possible
if(current_node is None):
return None
min_node = current_node
while(min_node.left):
min_node = min_node.left
return min_node
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print("Inorder Successor of 8 is : {}".format(inorder_successor(root, 8).val))
print("Inorder Successor of 10 is : {}".format(inorder_successor(root, 10).val))
print("Inorder Successor of 14 is : {}".format(inorder_successor(root, 14).val))
Output:
Given root of binary search tree and K as input, find K-th smallest element in BST.
Output:
Given two Binary Search Trees(BST), print the elements of both BSTs in sorted form.
The expected time complexity is O(m+n) where m is the number of nodes in first tree and n is the number of nodes in second tree.
Maximum allowed auxiliary space is O(height of the first tree + height of the second tree).
Output:
Given a Binary Tree, convert it to a Binary Search Tree.
The conversion must be done in such a way that keeps the original structure of Binary Tree.
Output:
Two of the nodes of a BST are swapped. Fix or correct the BST.
We can solve this in O(n) time and with a single traversal of the given BST.
Since inorder traversal of BST is always a sorted array, the problem can be reduced to a problem where two elements of a sorted array are swapped.
The swapped nodes are not adjacent in the inorder traversal of the BST.
Example: Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
Inorder traversal of the given tree: 3 25 7 8 10 15 20 5
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.
The swapped nodes are adjacent in the inorder traversal of BST.
Example: Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.
Output: