Scribd
Upload
14 views2 pages

Untitled 2

The document explains how to determine if a binary tree is a Binary Search Tree (BST) using inorder traversal and checks for value ordering. It also describes a method to find the closest value to a target in a BST and outlines steps to balance an unbalanced BST by converting it into a sorted array and reconstructing it. Example code snippets illustrate these concepts with tree node definitions and function implementations.

Uploaded by

Yash Behgal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
14 views2 pages

Untitled 2

The document explains how to determine if a binary tree is a Binary Search Tree (BST) using inorder traversal and checks for value ordering. It also describes a method to find the closest value to a target in a BST and outlines steps to balance an unbalanced BST by converting it into a sorted array and reconstructing it. Example code snippets illustrate these concepts with tree node definitions and function implementations.

Uploaded by

Yash Behgal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Question : check if a binary tree is a BST or not?

Answer : We can check whether a binary


tree is a BST or not by performing an inorder traversal of the binary tree and also checking
that the previous node's value is smaller than the current node's value.
# 5
# / \
# 3 7
# / \ / \
#1 4 6 8
root = TreeNode(5)
[Link] = TreeNode(3)
[Link] = TreeNode(7)
[Link] = TreeNode(1)
[Link] = TreeNode(4)
[Link] = TreeNode(6)
[Link] = TreeNode(8)

print(is_bst(root))
# Output: True

# 5
# / \
# 3 7
# / \ / \
# 1 6 4 8
[Link] = 6

print(is_bst(root))
# Output: False

Ques 2 : find the closest element in the bst ?? to find the closest element in a Binary Search
Tree to a given target value. we can perform we can perform transversal through the tree
while also keeping the track of the closest node enountered.

class TreeNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None

def closest_value(root, target):


closest = [Link]
while root:
if abs([Link] - target) < abs(closest - target):
closest = [Link]
root = [Link] if target < [Link] else [Link]
return closest

We can balance an unbalnce BST by


1. take inputs of nodes from the binary tree.
1. now we should define a function to find the height of tree.
2. now we should define a Boolean function to check recursively if the height
difference of left subtree and right subtree is not more than '1', then return True.
class TreeNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None

def inorder_traversal(root, result):


if root:
inorder_traversal([Link], result)
[Link]([Link])
inorder_traversal([Link], result)

def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
[Link] = sorted_array_to_bst(nums[:mid])
[Link] = sorted_array_to_bst(nums[mid+1:])
return root

def balance_bst(root):
sorted_elements = []
inorder_traversal(root, sorted_elements)
return sorted_array_to_bst(sorted_elements)

root = TreeNode(101)
[Link] = TreeNode(52)
[Link] = TreeNode(223)
[Link] = TreeNode(258)

balanced_root = balance_bst(root)

You might also like