Binary Search Tree Flashcards
What is a Binary Search Tree?
BST, like a BT, is a rooted tree, stores a key, and left and right subtree.
Properies:
each node must be greater than all keys in the left subtree and not greater that all key in the right subtree
write a recursive function to insert key and construct a BST from a list.
we examine the root and recursively insert the new node to the left subtree if its key is less than that of the root or the right subtree if its key is greater than or equal to the root.
class Node:
left = right = None
# Function to create a new binary tree node having a given key
def \_\_init\_\_(self, data):
self.data = data
# Function to perform inorder traversal on the tree def inorder(root):
if root is None:
return
inorder(root.left)
print(root.data, end=' ')
inorder(root.right)
# Recursive function to insert a key into a BST def insert(root, key):
# if the root is None, create a new node and return it
if root is None:
return Node(key)
# if the given key is less than the root node,
# recur for the left subtree
if key < root.data:
root.left = insert(root.left, key)
# otherwise, recur for the right subtree
else:
# key >= root.data
root.right = insert(root.right, key)
return root
# Function to construct a BST from given keys
def constructBST(keys):
root = None
for key in keys:
root = insert(root, key)
return root
if __name__ == ‘__main__’:
keys = [15, 10, 20, 8, 12, 16, 25] root = constructBST(keys) inorder(root)
Write an iterative function to insert the key in a binary tree and construct a binary search tree.
In iterative solution we keep recording of the parent node.
1) if root is none: make a node and return root
2) parent = None, cur = root
3) while root: parent = cur
of key < cur.data: cur = cur.left
Write an iterative function to insert the key in a binary tree and construct a binary search tree.
In iterative solution we keep recording of the parent node.
1) if root is none: make a node and retur root
2) parent = None, cur = root
3) while root: parent = cur
if key < cur.data: cur = cur.left
else: cur = cur.left
4) check parent.data with key to insert the key to the left or right of key
############### code
# A class to store a BST node
class Node:
# Function to create a new binary tree node having a given key
def \_\_init\_\_(self, key):
self.data = key
self.left = self.right = None
# Function to perform inorder traversal on the tree def inorder(root):
if root is None:
return
inorder(root.left)
print(root.data, end=' ')
inorder(root.right)
# Iterative function to insert a key into a BST def insertIterative(root, key):
# start with the root node
curr = root
# pointer to store the parent of the current node
parent = None
# if the tree is empty, create a new node and set it as root
if root is None:
return Node(key)
# traverse the tree and find the parent node of the given key
while curr:
# update the parent to the current node
parent = curr
# if the given key is less than the current node,
# go to the left subtree; otherwise, go to the right subtree.
if key < curr.data:
curr = curr.left
else:
curr = curr.right
# construct a node and assign it to the appropriate parent pointer
if key < parent.data:
parent.left = Node(key)
else:
parent.right = Node(key)
return root
# Function to construct a BST from given keys
def constructBST(keys):
root = None
for key in keys:
root = insertIterative(root, key)
return root
if __name__ == ‘__main__’:
keys = [15, 10, 20, 8, 12, 16, 25] root = constructBST(keys) inorder(root)
Search a given key in BST, recursive
We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful, we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached, then the key is not present in the tree.
On average, binary search trees with n nodes have O(log(n)) height. However, in the worst case, binary search trees can have O(n) height (for skewed trees where all the nodes except the leaf have one and only one child) when the unbalanced tree resembles a linked list. ############ code
# Recursive function to search in a given BST def search(root, key, parent):
# if the key is not present in the key
if root is None:
print('Key not found')
return
# if the key is found
if root.data == key:
if parent is None:
print(f'The node with key {key} is root node')
elif key < parent.data:
print('The given key is the left node of the node with key', parent.data)
else:
print('The given key is the right node of the node with key', parent.data)
return
# if the given key is less than the root node, recur for the left subtree;
# otherwise, recur for the right subtree
if key < root.data:
search(root.left, key, root)
else:
search(root.right, key, root)
if __name__ == ‘__main__’:
keys = [15, 10, 20, 8, 12, 16, 25]
root = None
for key in keys:
root = insert(root, key)
search(root, 25, None)
Search a given key in BST,iterative
def searchIterative(root, key):
# start with the root node
curr = root
# pointer to store the parent of the current node
parent = None
# traverse the tree and search for the key
while curr and curr.data != key:
# update the parent to the current node
parent = curr
# if the given key is less than the current node, go to the left subtree;
# otherwise, go to the right subtree
if key < curr.data:
curr = curr.left
else:
curr = curr.right
# if the key is not present in the key
if curr is None:
print('Key not found')
return
if parent is None:
print(f'The node with key {key} is root node')
elif key < parent.data:
print('The given key is the left node of the node with key', parent.data)
else:
print('The given key is the right node of the node with key', parent.data)
if __name__ == ‘__main__’:
keys = [15, 10, 20, 8, 12, 16, 25]
root = None
for key in keys:
root = insert(root, key)
searchIterative(root, 25)
Delet a Node in a Binary serach tree, iterative
we need two function:
1) finding minimum from a tree, it is going to be a successor of a deleted node if deleted node has both left and right child
2) the main delting function
In writing delting function,
we have search function (parent and current), the we consider three situation:
1) Case 1: Deleting a node with no children: remove the node from the tree. parent.left =None or parent.right = Node
2) Case 2: Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its inorder successor node or its inorder predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If we choose the inorder successor of a node, as the right subtree is not NULL (our present case is a node with 2 children), then its inorder successor is a node with the least value in its right subtree, which will have at a maximum of 1 subtree, so deleting it would fall in one of the first 2 cases.
3) Case 3: Deleting a node with one child: remove the node and replace it with its child.
################### code
# Helper function to find minimum value node in the subtree rooted at `curr`
def getMinimumKey(curr):
while curr.left:
curr = curr.left
return curr
#\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
# Function to delete a node from a BST
def deleteNode(root, key):
# pointer to store the parent of the current node
parent = None
# start with the root node
curr = root
# search key in the BST and set its parent pointer
while curr and curr.data != key:
# update the parent to the current node
parent = curr
# if the given key is less than the current node, go to the left subtree;
# otherwise, go to the right subtree
if key < curr.data:
curr = curr.left
else:
curr = curr.right
# return if the key is not found in the tree
if curr is None:
return root
# Case 1: node to be deleted has no children, i.e., it is a leaf node
if curr.left is None and curr.right is None:
# if the node to be deleted is not a root node, then set its
# parent left/right child to None
if curr != root:
if parent.left == curr:
parent.left = None
else:
parent.right = None
# if the tree has only a root node, set it to None
else:
root = None
# Case 2: node to be deleted has two children
elif curr.left and curr.right:
# find its inorder successor node
successor = getMinimumKey(curr.right)
# store successor value
val = successor.data
# recursively delete the successor. Note that the successor
# will have at most one child (right child)
deleteNode(root, successor.data)
# copy value of the successor to the current node
curr.data = val
# Case 3: node to be deleted has only one child
else:
# choose a child node
if curr.left:
child = curr.left
else:
child = curr.right
# if the node to be deleted is not a root node, set its parent
# to its child
if curr != root:
if curr == parent.left:
parent.left = child
else:
parent.right = child
# if the node to be deleted is a root node, then set the root to the child
else:
root = child
return root
Delet a Node from BST recursively
Function to find the maximum value node in the subtree rooted at `ptr`
def findMaximumKey(ptr):
while ptr.right:
ptr = ptr.right
return ptr
#\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ # Function to delete a node from a BST def deleteNode(root, key):
# base case: the key is not found in the tree
if root is None:
return root
# if the given key is less than the root node, recur for the left subtree
if key < root.data:
root.left = deleteNode(root.left, key)
# if the given key is more than the root node, recur for the right subtree
elif key > root.data:
root.right = deleteNode(root.right, key)
# key found
else:
# Case 1: node to be deleted has no children (it is a leaf node)
if root.left is None and root.right is None:
# update root to None
return None
# Case 2: node to be deleted has two children
elif root.left and root.right:
# find its inorder predecessor node
predecessor = findMaximumKey(root.left)
# copy value of the predecessor to the current node
root.data = predecessor.data
# recursively delete the predecessor. Note that the
# predecessor will have at most one child (left child)
root.left = deleteNode(root.left, predecessor.data)
# Case 3: node to be deleted has only one child
else:
# choose a child node
child = root.left if root.left else root.right
root = child
return root
Construct a balanced BST from the given keys
Given an unsorted integer array that represents binary search tree (BST) keys, construct a height-balanced BST from it. For each node of a height-balanced tree, the difference between its left and right subtree height is at most 1.
The height of such BST in the worst-case can be as much as the total number of keys in the BST. The worst case happens when given keys are sorted in ascending or descending order, and we get a skewed tree where all the nodes except the leaf have one and only one child.
For height-balanced BSTs, with each comparison, skip about half of the tree so that each insertion operation takes time proportional to the logarithm of the total number of items n stored in the tree, i.e., log2n. This is much better than the linear time required to find items by key in an (unsorted) array or unbalanced trees.
We can easily modify the solution to get height-balanced BSTs if all keys are known in advance. The idea is to sort the given keys first. Then the root will be the middle element of the sorted array, and we recursively construct the left subtree of the root by keys less than the middle element and the right subtree of the root by keys more than the middle element.
The time complexity of the solution is O(n.log(n)), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
code########
# A class to store a BST node
class Node:
def \_\_init\_\_(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Function to perform inorder traversal on the tree
def inorder(root):
if root is None:
return
inorder(root.left) print(root.data, end=' ') inorder(root.right)
# Function to construct balanced BST from the given sorted list def construct(keys, low, high, root):
# base case
if low > high:
return root
# find the middle element of the current range
mid = (low + high) // 2
# construct a new node from the middle element and assign it to the root
root = Node(keys[mid])
# left subtree of the root will be formed by keys less than middle element
root.left = construct(keys, low, mid - 1, root.left)
# right subtree of the root will be formed by keys more than the middle element
root.right = construct(keys, mid + 1, high, root.right)
return root
# Function to construct balanced BST from the given unsorted list def constructBST(keys):
# sort the keys first
keys.sort()
# construct a balanced BST and return the root node of the tree
return construct(keys, 0, len(keys) - 1, None)
if __name__ == ‘__main__’:
# input keys
keys = [15, 10, 20, 8, 12, 16, 25]
# construct a balanced binary search tree
root = constructBST(keys)
# print the keys in an inorder fashion
inorder(root)
Determine whether a given binary tree is a BST or not- using recursive and greedy seacrch
nstead of deciding based solely on a node’s values and its children, we also need information flowing down from the parent. In the tree above, if we could remember about the node containing the value 20, we would see that the node with value 5 is violating the BST property contract.
So, the condition we need to check at each node is:
If the node is the left child of its parent, it must be smaller than (or equal to) the parent, and it must pass down the value from its parent to its right subtree to make sure none of the nodes in that subtree is greater than the parent.
If the node is the right child of its parent, it must be larger than the parent, and it must pass down the value from its parent to its left subtree to make sure none of the nodes in that subtree is lesser than the parent.
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
code
def isBST(node, minKey, maxKey):
# base case
if node is None:
return True
# if the node's value falls outside the valid range
if node.data < minKey or node.data > maxKey:
return False
# recursively check left and right subtrees with an updated range
return isBST(node.left, minKey, node.data) and \
isBST(node.right, node.data, maxKey)
# Function to determine whether a given binary tree is a BST def checkForBST(root):
if isBST(root, -sys.maxsize, sys.maxsize):
print('The tree is a BST.')
else:
print('The tree is not a BST')
def swap(root):
left = root.left root. left = root.right root. right = left
Determine whether a given binary tree is a BST or not-
Using inorder subtree
We know that an inorder traversal of a binary search tree returns the nodes in sorted order. To determine whether a given binary tree is a BST, keep track of the last visited node while traversing the tree. Then for each encountered node in the inorder traversal, check whether the last visited node is smaller (or smaller/equal, if duplicates are to be allowed in the tree) compared to the current node.
code ##############
def isBST(root, prev):
# base case: empty tree is a BST
if root is None:
return True
# check if the left subtree is BST or not
left = isBST(root.left, prev)
# value of the current node should be more than that of the previous node
if root.data <= prev.data:
return False
# update previous node data and check if the right subtree is BST or not
prev.data = root.data
return left and isBST(root.right, prev)
# Function to determine whether a given binary tree is a BST def checkForBST(node):
# pointer to store previously processed node in the inorder traversal
prev = Node(-sys.maxsize)
# check if nodes are processed in sorted order
if isBST(node, prev):
print('The tree is a BST!')
else:
print('The tree is not a BST!')
Check if the given keys represent the same BSTs or not without building BST
Given two integer arrays, X and Y, representing a set of BST keys, check if they represent the same BSTs or not without building the tree. Assume that the keys are inserted into the BST in the same order as they appear in the array.
the time and sapve complexity is O(n2)
def isSameBST(X, Y, n):
# if no element is present in the list, return true
if n == 0:
return True
# if the first element differs in both lists (root node key), return false
if X[0] != Y[0]:
return False
# if the list contains only one key, return true
if n == 1:
return True
# take four auxiliary spaces of size `n-1` each (as maximum keys in # left or right subtree can be `n-1`) leftX = [None] * (n - 1) rightX = [None] * (n - 1) leftY = [None] * (n - 1) rightY = [None] * (n - 1) k = l = m = o = 0
# process the remaining keys and divide them into two groups
for i in range(1, n):
# `leftX` will contain all elements less than `X[0]`
if X[i] < X[0]:
leftX[k] = X[i]
k = k + 1
# `rightX` will contain all elements more than `X[0]`
else:
rightX[l] = X[i]
l = l + 1
# `leftY` will contain all elements less than `Y[0]`
if Y[i] < Y[0]:
leftY[m] = Y[i]
m = m + 1
# `rightY` will contain all elements more than `Y[0]`
else:
rightY[o] = Y[i]
o = o + 1
# return false if the size of `leftX` and `leftY` differs, i.e.,
# the total number of nodes in the left subtree of both trees differs
if k != m:
return False
# return false if the size of `rightX` and `rightY` differs, i.e.,
# the total number of nodes in the right subtree of both trees differs
if l != o:
return False
# check left and right subtree
return isSameBST(leftX, leftY, k) and isSameBST(rightX, rightY, l)
What is the Inorder Predecessor and Succssesor of a binary tree?
When you do inorder traversal of a Binary Tree, the neighbours of the given node are called predecessor and Successor.
Predecsessor: the right most element in the left subtree (findingMaximum(cur):
while cur.right:
cur = cur.right
return cur
Note: you call this function on cur.left)
Successor: The left most element in the right tree.
FindMinimum(cur):
while cur.left:
cur = cur.left
return cur
Note: you call this function on cur.right)
Find inorder predecessor for the given key in a BST
Given a BST, find the inorder predecessor of a given key in it. If the key does not lie in the BST, return the previous greater node (if any) present in the BST.
_______________________-
Inorder predecessor of a node locates on left subtree, right most child.
if the right most child is None, we need to find the ancesstor of a node is predecessor, i.e, the node visited before the given key.
If any such node is found, then the inorder predecessor is its parent;
otherwise it does not exist
O(n)
################## code############
# Function to find the maximum value node in a given BST
def findMaximum(root):
while root.right:
root = root.right
return root
# Iterative function to find inorder predecessor for a given key in a BST def findPredecessor(root, key):
# base case
if not root:
return None
prec = None while True:
# if the given key is less than the root node, visit the left subtree
if key < root.data:
root = root.left
# if the given key is more than the root node, visit the right subtree
elif key > root.data:
# update predecessor to the current node before visiting
# right subtree
prec = root
root = root.right
# if a node with the desired value is found, the predecessor is the maximum
# value node in its left subtree (if any)
else:
if root.left:
prec = findMaximum(root.left)
break
# if the key doesn't exist in the binary tree, return previous greater node
if root is None:
return prec
# return predecessor, if any
return prec
# A class to store a BST node
class Node:
def \_\_init\_\_(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Recursive function to insert a key into a BST def insert(root, key):
# if the root is None, create a new node and return it
if root is None:
return Node(key)
# if the given key is less than the root node, recur for the left subtree
if key < root.data:
root.left = insert(root.left, key)
# if the given key is more than the root node, recur for the right subtree
else:
root.right = insert(root.right, key)
return root
if __name__ == ‘__main__’:
keys = [15, 10, 20, 8, 12, 16, 25]
''' Construct the following tree
15
/ \
/ \
10 20
/ \ / \
/ \ / \
8 12 16 25
'''
root = None
for key in keys:
root = insert(root, key)
# find inorder predecessor for each key
for key in keys:
prec = findPredecessor(root, key)
if prec:
print(f'Predecessor of node {key} is {prec.data}')
else:
print('The predecessor does
write a function to search a key throughout a tree, return False if there is not such a node
def search(root, key):
traverse the tree and search for the key
while root:
# if the given key is less than the current node, go to the left
# subtree; otherwise, go to the right subtree
if root.data > key.data:
root = root.left
elif root.data < key.data:
root = root.right
# if node is found
elif root.data == key.data:
return True
return False
