User monish123123

About

1.Program to Search for an Element in a Binary Search Tree class Node: def _init_(self, data): self.data = data self.left = None self.right = None

def search(root, key):

# Base case: the tree is empty or the key is found at the root
if root is None or root.data == key:
    return root

# Key is greater than the root's data, so search in the right subtree
if root.data < key:
    return search(root.right, key)

# Key is smaller than the root's data, so search in the left subtree
return search(root.left, key)

Example usage

Create the binary search tree

root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8)

Search for an element

element = 4 result = search(root, element) if result: print(f"Element {element} found in the binary search tree.") else: print(f"Element {element} not found in the binary search tree.")

Ans: class Node: def __init__(self, data): self.data = data self.left = None self.right = None

def search(root, key):

# Base case: the tree is empty or the key is found at the root
if root is None or root.data == key:
    return root

# Key is greater than the root's data, so search in the right subtree
if root.data < key:
    return search(root.right, key)

# Key is smaller than the root's data, so search in the left subtree
return search(root.left, key)

Example usage

Create the binary search tree

root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8)

Search for an element

element = 4 result = search(root, element) if result: print(f"Element {element} found in the binary search tree.") else: print(f"Element {element} not found in the binary search tree.")

2.Program to Implement Self Balancing Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None self.height = 1

class AVLTree: def _init_(self): self.root = None

def insert(self, key):
    self.root = self._insert_helper(self.root, key)

def _insert_helper(self, node, key):
    if node is None:
        return TreeNode(key)
    elif key < node.key:
        node.left = self._insert_helper(node.left, key)
    else:
        node.right = self._insert_helper(node.right, key)

    node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
    balance_factor = self._get_balance_factor(node)

    if balance_factor > 1:
        if key < node.left.key:
            return self._rotate_right(node)
        else:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
    if balance_factor < -1:
        if key > node.right.key:
            return self._rotate_left(node)
        else:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

    return node

def _get_height(self, node):
    if node is None:
        return 0
    return node.height

def _get_balance_factor(self, node):
    if node is None:
        return 0
    return self._get_height(node.left) - self._get_height(node.right)

def _rotate_left(self, z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

    return y

def _rotate_right(self, z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

    return y

def display(self):
    self._display_helper(self.root)

def _display_helper(self, node, level=0):
    if node is not None:
        self._display_helper(node.right, level + 1)
        print('  ' * level + '->', node.key)
        self._display_helper(node.left, level + 1)

tree = AVLTree() tree.insert(10) tree.insert(20) tree.insert(30) tree.insert(40) tree.insert(50) tree.insert(25)

tree.display()

2.ANS:

class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1

class AVLTree: def __init__(self): self.root = None

def insert(self, key):
    self.root = self._insert_helper(self.root, key)

def _insert_helper(self, node, key):
    if node is None:
        return TreeNode(key)
    elif key < node.key:
        node.left = self._insert_helper(node.left, key)
    else:
        node.right = self._insert_helper(node.right, key)

    node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
    balance_factor = self._get_balance_factor(node)

    if balance_factor > 1:
        if key < node.left.key:
            return self._rotate_right(node)
        else:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
    if balance_factor < -1:
        if key > node.right.key:
            return self._rotate_left(node)
        else:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

    return node

def _get_height(self, node):
    if node is None:
        return 0
    return node.height

def _get_balance_factor(self, node):
    if node is None:
        return 0
    return self._get_height(node.left) - self._get_height(node.right)

def _rotate_left(self, z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

    return y

def _rotate_right(self, z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
    y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

    return y

def display(self):
    self._display_helper(self.root)

def _display_helper(self, node, level=0):
    if node is not None:
        self._display_helper(node.right, level + 1)
        print('  ' * level + '->', node.key)
        self._display_helper(node.left, level + 1)

tree = AVLTree() tree.insert(10) tree.insert(20) tree.insert(30) tree.insert(40) tree.insert(50) tree.insert(25)

tree.display()

3.Program to Check if a Binary Search Tree is balanced or not. class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None

def is_balanced(root): if root is None: return True

left_height = get_height(root.left)
right_height = get_height(root.right)

if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
    return True

return False

def get_height(node): if node is None: return 0

left_height = get_height(node.left)
right_height = get_height(node.right)

return max(left_height, right_height) + 1

Example usage:

Balanced BST

root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(15) root.left.left = TreeNode(2) root.left.right = TreeNode(8) root.right.left = TreeNode(12) root.right.right = TreeNode(20)

print(is_balanced(root)) # Output: True

Unbalanced BST

root_unbalanced = TreeNode(10) root_unbalanced.left = TreeNode(5) root_unbalanced.left.left = TreeNode(2) root_unbalanced.left.left.left = TreeNode(1)

print(is_balanced(root_unbalanced)) # Output: False 3.ANS:

Ikkada aa code right ani vachindhi and output matram first true and second false ani vachindhi!!

4.Program to Find the Lowest Common Ancestor of a Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None

def find_lca(root, node1, node2): if root is None: return None

# If both nodes are smaller, LCA must be in the left subtree
if root.key > node1.key and root.key > node2.key:
    return find_lca(root.left, node1, node2)

# If both nodes are greater, LCA must be in the right subtree
if root.key < node1.key and root.key < node2.key:
    return find_lca(root.right, node1, node2)

# If above conditions don't apply, the current node is the LCA
return root

Example usage:

Create a BST

root = TreeNode(20) root.left = TreeNode(8) root.right = TreeNode(22) root.left.left = TreeNode(4) root.left.right = TreeNode(12) root.left.right.left = TreeNode(10) root.left.right.right = TreeNode(14)

Nodes to find LCA for

node1 = TreeNode(10) node2 = TreeNode(14)

lca = find_lca(root, node1, node2) if lca is not None: print("Lowest Common Ancestor:", lca.key) else: print("Lowest Common Ancestor not found.")

4.ANS: OUTPUT:

Lowest Common Ancestor: 12
Code wuestion lo vunnade vachindhi!!

5.Program to Find the Greatest Common Ancestor of a Binary Search Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None

def find_gca(root, node1, node2): if root is None: return None

# If both nodes are smaller, GCA must be in the left subtree
if root.key > node1.key and root.key > node2.key:
    return find_gca(root.left, node1, node2)

# If both nodes are greater, GCA must be in the right subtree
if root.key < node1.key and root.key < node2.key:
    return find_gca(root.right, node1, node2)

# If one node is smaller and the other is greater, or
# one node matches the root value, the current node is the GCA
return root

Example usage:

Create a BST

Nodes to find GCA for

node1 = TreeNode(10) node2 = TreeNode(14)

gca = find_gca(root, node1, node2) if gca is not None: print("Greatest Common Ancestor:", gca.key) else: print("Greatest Common Ancestor not found.")

ANS: class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None

def find_gca(root, node1, node2): if root is None: return None

# If both nodes are smaller, GCA must be in the left subtree
if root.key > node1.key and root.key > node2.key:
    return find_gca(root.left, node1, node2)

# If both nodes are greater, GCA must be in the right subtree
if root.key < node1.key and root.key < node2.key:
    return find_gca(root.right, node1, node2)

# If one node is smaller and the other is greater, or
# one node matches the root value, the current node is the GCA
return root

Example usage:

Create a BST

Nodes to find GCA for

node1 = TreeNode(10) node2 = TreeNode(14)

gca = find_gca(root, node1, node2) if gca is not None: print("Greatest Common Ancestor:", gca.key) else: print("Greatest Common Ancestor not found.")

OUTPUT: Greatest Common Ancestor: 12

6.Program for Spiral Order Traversal of a Tree using Recursion class Node: def init(self, data): self.right=None self.left=None self.data=data

def height(root): if root is None: return 0 else: return max(height(root.left), height(root.right))+1

def spiral(root): h=height(root) direction=1 for i in range(1, h+1): spiral_order(root, i, direction) direction = -direction

def spiral_order(root, level=1, direction=1): if root is None: return None if level==1: print(root.data,end="") elif level>1: if direction==1: spiral_order(root.left, level-1, direction) spiral_order(root.right, level-1, direction) else: spiral_order(root.right, level-1, direction) spiral_order(root.left, level-1, direction)

root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) root.right.left=Node(6) root.right.right=Node(7)

spiral(root)

ANS: class Node: def __init__(self, data): self.right = None self.left = None self.data = data

def height(root): if root is None: return 0 else: return max(height(root.left), height(root.right)) + 1

def spiral(root): h = height(root) direction = 1 for i in range(1, h+1): spiral_order(root, i, direction) direction = -direction

def spiral_order(root, level=1, direction=1): if root is None: return None if level == 1: print(root.data, end=" ") elif level > 1: if direction == 1: spiral_order(root.left, level-1, direction) spiral_order(root.right, level-1, direction) else: spiral_order(root.right, level-1, direction) spiral_order(root.left, level-1, direction)

root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7)

spiral(root)

OUTPUT: 1 3 2 4 5 6 7

7.Program to Find Deepest Left Leaf in a Binary Tree class TreeNode: def _init_(self, key): self.key = key self.left = None self.right = None

def find_deepest_left_leaf(root): max_depth = 0 deepest_left_leaf = None

def dfs(node, depth, is_left):
    nonlocal max_depth, deepest_left_leaf

    if node is None:
        return

    if is_left and node.left is None and node.right is None and depth > max_depth:
        max_depth = depth
        deepest_left_leaf = node

    dfs(node.left, depth + 1, True)
    dfs(node.right, depth + 1, False)

dfs(root, 0, False)
return deepest_left_leaf

Example usage:

Create a binary tree

root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.right = TreeNode(6) root.left.right.left = TreeNode(7) root.right.right.left = TreeNode(8) root.right.right.right = TreeNode(9)

deepest_left = find_deepest_left_leaf(root) if deepest_left is not None: print("Deepest left leaf:", deepest_left.key) else: print("No left leaf found.")

ANS: class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None

def find_deepest_left_leaf(root): max_depth = 0 deepest_left_leaf = None

def dfs(node, depth, is_left):
    nonlocal max_depth, deepest_left_leaf

    if node is None:
        return

    if is_left and node.left is None and node.right is None and depth > max_depth:
        max_depth = depth
        deepest_left_leaf = node

    dfs(node.left, depth + 1, True)
    dfs(node.right, depth + 1, False)

dfs(root, 0, False)
return deepest_left_leaf

Example usage:

Create a binary tree

deepest_left = find_deepest_left_leaf(root) if deepest_left is not None: print("Deepest left leaf:", deepest_left.key) else: print("No left leaf found.")

OUTPUT: Deepest left leaf: 7

8.Program to Create Mirror Image of a Binary Tree class Node: def init(self, data): self.data=data self.right=None self.left=None def mirrorimage(root): if root is None: return None else: root.left, root.right=root.right, root.left mirrorimage(root.left) mirrorimage(root.right) return def printbt(root): if root: print(root.data,"-->",end="") printbt(root.left) printbt(root.right) return print("\n")

root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) root.right.left=Node(6) root.right.right=Node(7) printbt(root) mirrorimage(root) printbt(root)

ANS: OUTPUT: 1 -->2 -->4 -->5 -->3 -->6 -->7 --> 1 -->3 -->7 -->6 -->2 -->5 -->4 -->

9.Program to Implement Heap class MinHeap: def _init_(self): self.heap = []

def parent(self, i):
    return (i - 1) // 2

def left_child(self, i):
    return 2 * i + 1

def right_child(self, i):
    return 2 * i + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, item):
    self.heap.append(item)
    self._heapify_up(len(self.heap) - 1)

def _heapify_up(self, i):
    while i != 0 and self.heap[i] < self.heap[self.parent(i)]:
        self.swap(i, self.parent(i))
        i = self.parent(i)

def extract_min(self):
    if len(self.heap) == 0:
        return None
    if len(self.heap) == 1:
        return self.heap.pop()

    root = self.heap[0]
    self.heap[0] = self.heap.pop()
    self._heapify_down(0)
    return root

def _heapify_down(self, i):
    smallest = i
    left = self.left_child(i)
    right = self.right_child(i)

    if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != i:
        self.swap(i, smallest)
        self._heapify_down(smallest)

def display(self):
    print(self.heap)

Example usage:

heap = MinHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)

heap.display() # Output: [5, 10, 15, 30, 25, 20]

min_value = heap.extract_min() print(min_value) # Output: 5

heap.display() # Output: [10, 20, 15, 30, 25]

ANS: class MinHeap: def __init__(self): self.heap = []

def parent(self, i):
    return (i - 1) // 2

def left_child(self, i):
    return 2 * i + 1

def right_child(self, i):
    return 2 * i + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, item):
    self.heap.append(item)
    self._heapify_up(len(self.heap) - 1)

def _heapify_up(self, i):
    while i != 0 and self.heap[i] < self.heap[self.parent(i)]:
        self.swap(i, self.parent(i))
        i = self.parent(i)

def extract_min(self):
    if len(self.heap) == 0:
        return None
    if len(self.heap) == 1:
        return self.heap.pop()

    root = self.heap[0]
    self.heap[0] = self.heap.pop()
    self._heapify_down(0)
    return root

def _heapify_down(self, i):
    smallest = i
    left = self.left_child(i)
    right = self.right_child(i)

    if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != i:
        self.swap(i, smallest)
        self._heapify_down(smallest)

def display(self):
    print(self.heap)

Example usage:

heap = MinHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)

heap.display() # Output: [5, 10, 15, 30, 25, 20]

min_value = heap.extract_min() print(min_value) # Output: 5

heap.display() # Output: [10, 20, 15, 30, 25]

10.Program to Implement Binary Heap class BinaryHeap: def _init_(self): self.heap = [] self.size = 0

def parent(self, i):
    return (i - 1) // 2

def left_child(self, i):
    return 2 * i + 1

def right_child(self, i):
    return 2 * i + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, item):
    self.heap.append(item)
    self.size += 1
    self._heapify_up(self.size - 1)

def _heapify_up(self, i):
    while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
        self.swap(i, self.parent(i))
        i = self.parent(i)

def extract_min(self):
    if self.size == 0:
        return None
    if self.size == 1:
        self.size -= 1
        return self.heap.pop()

    root = self.heap[0]
    self.heap[0] = self.heap.pop()
    self.size -= 1
    self._heapify_down(0)
    return root

def _heapify_down(self, i):
    smallest = i
    left = self.left_child(i)
    right = self.right_child(i)

    if left < self.size and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < self.size and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != i:
        self.swap(i, smallest)
        self._heapify_down(smallest)

def display(self):
    print(self.heap)

Example usage:

heap = BinaryHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)

heap.display() # Output: [5, 10, 15, 30, 25, 20]

min_value = heap.extract_min() print(min_value) # Output: 5

heap.display() # Output: [10, 20, 15, 30, 25]

ANS: question lo vunna code coreect ani vachindhi rakapothe msg chei check chestaa

Program to Implement Weak Heap class WeakHeap: def _init_(self):

self.heap = []
self.size = 0

def is_empty(self):

return self.size == 0

def insert(self, key):

self.heap.append(key)
self.size += 1
self._heapify_up(self.size - 1)

def extract_min(self):

if self.is_empty():
    return None

root = self.heap[0]
self.heap[0] = self.heap.pop()
self.size -= 1
self._heapify_down(0)
return root

def _heapify_up(self, i):

while i > 0 and self.heap[i] < self.heap[(i - 1) // 2]:
    self.heap[i], self.heap[(i - 1) // 2] = self.heap[(i - 1) // 2], self.heap[i]
    i = (i - 1) // 2

def _heapify_down(self, i):

while True:
    left_child = 2 * i + 1
    right_child = 2 * i + 2
    smallest = i

    if left_child < self.size and self.heap[left_child] < self.heap[smallest]:
        smallest = left_child

    if right_child < self.size and self.heap[right_child] < self.heap[smallest]:
        smallest = right_child

    if smallest != i:
        self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
        i = smallest
    else:
        break

def display(self):

print(self.heap)

Example usage:

heap = WeakHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)

heap.display() # Output: [5, 10, 15, 30, 25, 20]

min_value = heap.extract_min() print(min_value) # Output: 5

heap.display() # Output: [10, 20, 15, 30, 25]

ANS: class WeakHeap: def __init__(self): self.heap = [] self.size = 0

def is_empty(self):
    return self.size == 0

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    self._heapify_up(self.size - 1)

def extract_min(self):
    if self.is_empty():
        return None

    root = self.heap[0]
    self.heap[0] = self.heap.pop()
    self.size -= 1
    self._heapify_down(0)
    return root

def _heapify_up(self, i):
    while i > 0 and self.heap[i] < self.heap[(i - 1) // 2]:
        self.heap[i], self.heap[(i - 1) // 2] = self.heap[(i - 1) // 2], self.heap[i]
        i = (i - 1) // 2

def _heapify_down(self, i):
    while True:
        left_child = 2 * i + 1
        right_child = 2 * i + 2
        smallest = i

        if left_child < self.size and self.heap[left_child] < self.heap[smallest]:
            smallest = left_child

        if right_child < self.size and self.heap[right_child] < self.heap[smallest]:
            smallest = right_child

        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest
        else:
            break

def display(self):
    print(self.heap)

Example usage:

heap = WeakHeap() heap.insert(10) heap.insert(20) heap.insert(15) heap.insert(30) heap.insert(25) heap.insert(5)

heap.display() # Output: [5, 10, 15, 30, 25, 20]

min_value = heap.extract_min() print(min_value) # Output: 5

heap.display() # Output: [10, 20, 15, 30, 25]

Program to Implement Fibonacci Heap class FibonacciHeapNode: def _init_(self, value):

self.value = value
self.parent = None
self.child = None
self.left = self
self.right = self
self.degree = 0
self.marked = False

class FibonacciHeap: def _init_(self): self.min_node = None self.size = 0

def insert(self, value):
    new_node = FibonacciHeapNode(value)
    if self.min_node is None:
        self.min_node = new_node
    else:
        self._insert_node(new_node, self.min_node)
        if new_node.value < self.min_node.value:
            self.min_node = new_node
    self.size += 1

def _insert_node(self, new_node, node):
    new_node.left = node
    new_node.right = node.right
    node.right = new_node
    new_node.right.left = new_node

def get_min(self):
    if self.min_node is None:
        return None
    return self.min_node.value

def extract_min(self):
    min_node = self.min_node
    if min_node is not None:
        child = min_node.child
        while child is not None:
            next_child = child.right
            self._insert_node(child, self.min_node)
            child.parent = None
            child = next_child

        min_node.left.right = min_node.right
        min_node.right.left = min_node.left

        if min_node == min_node.right:
            self.min_node = None
        else:
            self.min_node = min_node.right
            self._consolidate()

        self.size -= 1

    return min_node.value

def _consolidate(self):
    max_degree = int(self._log(self.size) * 2) + 1
    degree_table = [None] * max_degree

    node = self.min_node
    nodes_to_visit = [node]
    while nodes_to_visit:
        current = nodes_to_visit.pop()
        degree = current.degree

        while degree_table[degree] is not None:
            other = degree_table[degree]
            if current.value > other.value:
                current, other = other, current
            self._link(other, current)
            degree_table[degree] = None
            degree += 1

        degree_table[degree] = current

        if current != current.right:
            nodes_to_visit.append(current.right)

def _link(self, child, parent):
    child.left.right = child.right
    child.right.left = child.left

    child.parent = parent

    if parent.child is None:
        parent.child = child
        child.right = child
        child.left = child
    else:
        parent.child.left.right = child
        child.left = parent.child.left
        parent.child.left = child
        child.right = parent.child

    parent.degree += 1
    child.marked = False

def _log(self, x):
    return math.log(x) / math.log(2)

def decrease_key(self, node, new_value):
    if new_value > node.value:
        raise ValueError("New value is greater than the current value")

    node.value = new_value
    parent = node.parent

    if parent is not None and node.value < parent.value:
        self._cut(node, parent)
        self._cascading_cut(parent)

    if node.value < self.min_node.value:
    self.min_node = node
 def _cut(self, node, parent):
if node == node.right:
    parent.child = None
else:
    node.left.right = node.right
    node.right.left = node.left
    if parent.child == node:
        parent.child = node.right

parent.degree -= 1
node.left = node
node.right = node
node.parent = None
node.marked = False

self._insert_node(node, self.min_node)

def _cascading_cut(self, node): parent = node.parent if parent is not None: if not node.marked: node.marked = True else: self._cut(node, parent) self._cascading_cut(parent)

def is_empty(self): return self.size == 0

ANS: import math

class FibonacciHeapNode: def __init__(self, value): self.value = value self.parent = None self.child = None self.left = self self.right = self self.degree = 0 self.marked = False

class FibonacciHeap: def __init__(self): self.min_node = None self.size = 0

def insert(self, value):
    new_node = FibonacciHeapNode(value)
    if self.min_node is None:
        self.min_node = new_node
    else:
        self._insert_node(new_node, self.min_node)
        if new_node.value < self.min_node.value:
            self.min_node = new_node
    self.size += 1

def _insert_node(self, new_node, node):
    new_node.left = node
    new_node.right = node.right
    node.right = new_node
    new_node.right.left = new_node

def get_min(self):
    if self.min_node is None:
        return None
    return self.min_node.value

def extract_min(self):
    min_node = self.min_node
    if min_node is not None:
        child = min_node.child
        while child is not None:
            next_child = child.right
            self._insert_node(child, self.min_node)
            child.parent = None
            child = next_child

        min_node.left.right = min_node.right
        min_node.right.left = min_node.left

        if min_node == min_node.right:
            self.min_node = None
        else:
            self.min_node = min_node.right
            self._consolidate()

        self.size -= 1

    return min_node.value

def _consolidate(self):
    max_degree = int(self._log(self.size) * 2) + 1
    degree_table = [None] * max_degree

    node = self.min_node
    nodes_to_visit = [node]
    while nodes_to_visit:
        current = nodes_to_visit.pop()
        degree = current.degree

        while degree_table[degree] is not None:
            other = degree_table[degree]
            if current.value > other.value:
                current, other = other, current
            self._link(other, current)
            degree_table[degree] = None
            degree += 1

        degree_table[degree] = current

        if current != current.right:
            nodes_to_visit.append(current.right)

def _link(self, child, parent):
    child.left.right = child.right
    child.right.left = child.left

    child.parent = parent

    if parent.child is None:
        parent.child = child
        child.right = child
        child.left = child
    else:
        parent.child.left.right = child
        child.left = parent.child.left
        parent

Program to Implement Leftist Heap

class LeftistHeapNode: def _init_(self, value): self.value = value self.left = None self.right = None self.rank = 1

class LeftistHeap: def _init_(self): self.root = None

def merge(self, heap1, heap2):
    if heap1 is None:
        return heap2
    if heap2 is None:
        return heap1

    if heap1.value > heap2.value:
        heap1, heap2 = heap2, heap1

    heap1.right = self.merge(heap1.right, heap2)

    if heap1.left is None or heap1.left.rank < heap1.right.rank:
        heap1.left, heap1.right = heap1.right, heap1.left

    if heap1.right is None:
        heap1.rank = 1
    else:
        heap1.rank = heap1.right.rank + 1

    return heap1

def insert(self, value):
    node = LeftistHeapNode(value)
    self.root = self.merge(self.root, node)

def delete_min(self):
    if self.root is None:
        return None

    min_value = self.root.value
    self.root = self.merge(self.root.left, self.root.right)

    return min_value

def get_min(self):
    if self.root is None:
        return None

    return self.root.value

def is_empty(self):
    return self.root is None

Example usage

heap = LeftistHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

print("Min Value:", heap.get_min()) # Output: Min Value: 1

deleted_value = heap.delete_min() print("Deleted Value:", deleted_value) # Output: Deleted Value: 1

print("Min Value:", heap.get_min()) # Output: Min Value: 3

print("Is Empty:", heap.is_empty()) # Output: Is Empty: False

ANS: class LeftistHeapNode: def __init__(self, value): self.value = value self.left = None self.right = None self.rank = 1

class LeftistHeap: def __init__(self): self.root = None

def merge(self, heap1, heap2):
    if heap1 is None:
        return heap2
    if heap2 is None:
        return heap1

    if heap1.value > heap2.value:
        heap1, heap2 = heap2, heap1

    heap1.right = self.merge(heap1.right, heap2)

    if heap1.left is None or heap1.left.rank < heap1.right.rank:
        heap1.left, heap1.right = heap1.right, heap1.left

    if heap1.right is None:
        heap1.rank = 1
    else:
        heap1.rank = heap1.right.rank + 1

    return heap1

def insert(self, value):
    node = LeftistHeapNode(value)
    self.root = self.merge(self.root, node)

def delete_min(self):
    if self.root is None:
        return None

    min_value = self.root.value
    self.root = self.merge(self.root.left, self.root.right)

    return min_value

def get_min(self):
    if self.root is None:
        return None

    return self.root.value

def is_empty(self):
    return self.root is None

Example usage

heap = LeftistHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

print("Min Value:", heap.get_min()) # Output: Min Value: 1

deleted_value = heap.delete_min() print("Deleted Value:", deleted_value) # Output: Deleted Value: 1

print("Min Value:", heap.get_min()) # Output: Min Value: 3

print("Is Empty:", heap.is_empty()) # Output: Is Empty: False

Program to Implement Min Heap

class MinHeap: def _init_(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_min(self):
    if len(self.heap) == 0:
        return None

    min_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return min_value

def heapify_down(self, index):
    n = len(self.heap)
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < n and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def peek_min(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return len(self.heap)

def display(self):
    print("Min Heap:", self.heap)

Example usage

heap = MinHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

heap.display() # Output: Min Heap: [1, 5, 3, 10, 8]

min_value = heap.extract_min() print("Extracted Min Value:", min_value) # Output: Extracted Min Value: 1

heap.display() # Output: Min Heap: [3, 5, 8, 10]

peek_value = heap.peek_min() print("Peeked Min Value:", peek_value) # Output: Peeked Min Value: 3

print("Heap Size:", heap.size()) # Output: Heap Size: 4

ANS:class MinHeap: def __init__(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_min(self):
    if len(self.heap) == 0:
        return None

    min_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return min_value

def heapify_down(self, index):
    n = len(self.heap)
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < n and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def peek_min(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return

Program to Implement Max Heap

class MaxHeap: def _init_(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] > self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_max(self):
    if len(self.heap) == 0:
        return None

    max_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return max_value

def heapify_down(self, index):
    n = len(self.heap)
    largest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] > self.heap[largest]:
        largest = left

    if right < n and self.heap[right] > self.heap[largest]:
        largest = right

    if largest != index:
        self.swap(index, largest)
        self.heapify_down(largest)

def peek_max(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return len(self.heap)

def display(self):
    print("Max Heap:", self.heap)

Example usage

heap = MaxHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

heap.display() # Output: Max Heap: [10, 8, 3, 5, 1]

max_value = heap.extract_max() print("Extracted Max Value:", max_value) # Output: Extracted Max Value: 10

heap.display() # Output: Max Heap: [8, 5, 3, 1]

peek_value = heap.peek_max() print("Peeked Max Value:", peek_value) # Output: Peeked Max Value: 8

print("Heap Size:", heap.size()) # Output: Heap Size: 4

ANS:class MaxHeap: def __init__(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] > self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_max(self):
    if len(self.heap) == 0:
        return None

    max_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return max_value

def heapify_down(self, index):
    n = len(self.heap)
    largest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] > self.heap[largest]:
        largest = left

    if right < n and self.heap[right] > self.heap[largest]:
        largest = right

    if largest != index:
        self.swap(index, largest)
        self.heapify_down(largest)

def peek_max(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return len(self.heap)

def display(self):
    print("Max Heap:", self.heap)

Example usage

heap = MaxHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

heap.display() # Output: Max Heap: [10, 8, 3, 5, 1]

max_value = heap.extract_max() print("Extracted Max Value:", max_value) # Output: Extracted Max Value: 10

heap.display() # Output: Max Heap: [8, 5, 3, 1]

peek_value = heap.peek_max() print("Peeked Max Value:", peek_value) # Output: Peeked Max Value: 8

print("Heap Size:", heap.size()) # Output: Heap Size: 4

Program to Implement Min Heap

class MinHeap: def _init_(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_min(self):
    if len(self.heap) == 0:
        return None

    min_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return min_value

def heapify_down(self, index):
    n = len(self.heap)
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < n and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def peek_min(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return len(self.heap)

def display(self):
    print("Min Heap:", self.heap)

Example usage

heap = MinHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

heap.display() # Output: Min Heap: [1, 5, 3, 10, 8]

min_value = heap.extract_min() print("Extracted Min Value:", min_value) # Output: Extracted Min Value: 1

heap.display() # Output: Min Heap: [3, 5, 8, 10]

peek_value = heap.peek_min() print("Peeked Min Value:", peek_value) # Output: Peeked Min Value: 3

print("Heap Size:", heap.size()) # Output: Heap Size: 4

ANS:class MinHeap: def __init__(self): self.heap = []

def parent(self, index):
    return (index - 1) // 2

def left_child(self, index):
    return (2 * index) + 1

def right_child(self, index):
    return (2 * index) + 2

def swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def insert(self, value):
    self.heap.append(value)
    self.heapify_up(len(self.heap) - 1)

def heapify_up(self, index):
    while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
        parent_index = self.parent(index)
        self.swap(index, parent_index)
        index = parent_index

def extract_min(self):
    if len(self.heap) == 0:
        return None

    min_value = self.heap[0]
    self.swap(0, len(self.heap) - 1)
    self.heap.pop()
    self.heapify_down(0)

    return min_value

def heapify_down(self, index):
    n = len(self.heap)
    smallest = index
    left = self.left_child(index)
    right = self.right_child(index)

    if left < n and self.heap[left] < self.heap[smallest]:
        smallest = left

    if right < n and self.heap[right] < self.heap[smallest]:
        smallest = right

    if smallest != index:
        self.swap(index, smallest)
        self.heapify_down(smallest)

def peek_min(self):
    if len(self.heap) == 0:
        return None

    return self.heap[0]

def size(self):
    return len(self.heap)

def display(self):
    print("Min Heap:", self.heap)

Example usage

heap = MinHeap() heap.insert(5) heap.insert(10) heap.insert(3) heap.insert(8) heap.insert(1)

heap.display() # Output: Min Heap: [1, 5, 3, 10, 8]

min_value = heap.extract_min() print("Extracted Min Value:", min_value) # Output: Extracted Min Value: 1

heap.display() # Output: Min Heap: [3, 5, 8, 10]

peek_value = heap.peek_min() print("Peeked Min Value:", peek_value) # Output: Peeked Min Value: 3

print("Heap Size:", heap.size()) # Output: Heap Size: 4

17.Program to Print the Nodes at Odd Levels of a Tree class Node: def init(self, data): self.right=None self.left=None self.data=data

def oddNode(root,level): if root is None: return 0 else: if(level%2!=0): print(root.data) oddNode(root.left,level+1) oddNode(root.right,level+1)

root=Node(5) root.left=Node(3) root.right=Node(9) root.left.left=Node(4) root.left.right=Node(1) oddNode(root,1)

ANS:class Node: def __init__(self, data): self.right = None self.left = None self.data = data

def oddNode(root, level=1): if root is None: return if level % 2 != 0: print(root.data) oddNode(root.left, level + 1) oddNode(root.right, level + 1)

Example usage

root = Node(5) root.left = Node(3) root.right = Node(9) root.left.left = Node(4) root.left.right = Node(1)

oddNode(root)

Program to Create Expression Tree from Infix Expression

class Node: def _init_(self, value): self.value = value self.left = None self.right = None

def is_operator(char): return char in ['+', '-', '*', '/']

def precedence(char): if char == '+' or char == '-': return 1 elif char == '*' or char == '/': return 2 else: return 0

def infix_to_postfix(expression): postfix = [] stack = []

for char in expression:
    if char.isalnum():
        postfix.append(char)
    elif char == '(':
        stack.append(char)
    elif char == ')':
        while stack and stack[-1] != '(':
            postfix.append(stack.pop())
        stack.pop()  # Discard '('
    elif is_operator(char):
        while stack and stack[-1] != '(' and precedence(char) <= precedence(stack[-1]):
            postfix.append(stack.pop())
        stack.append(char)

while stack:
    postfix.append(stack.pop())

return ''.join(postfix)

def build_expression_tree(postfix): stack = []

for char in postfix:
    if char.isalnum():
        node = Node(char)
        stack.append(node)
    elif is_operator(char):
        right = stack.pop()
        left = stack.pop()
        node = Node(char)
        node.left = left
        node.right = right
        stack.append(node)

return stack.pop()

def inorder_traversal(root): if root is None: return

inorder_traversal(root.left)
print(root.value, end=' ')
inorder_traversal(root.right)

Example usage

expression = "a+bc-(d/e+fg)"

postfix = infix_to_postfix(expression) print("Postfix expression:", postfix)

root = build_expression_tree(postfix)

print("Inorder traversal of the expression tree:") inorder_traversal(root)

ANS:

class Node: def __init__(self, value): self.value = value self.left = None self.right = None

def is_operator(char): return char in ['+', '-', '*', '/']

def precedence(char): if char == '+' or char == '-': return 1 elif char == '*' or char == '/': return 2 else: return 0

def infix_to_postfix(expression): postfix = [] stack = []

for char in expression:
    if char.isalnum():
        postfix.append(char)
    elif char == '(':
        stack.append(char)
    elif char == ')':
        while stack and stack[-1] != '(':
            postfix.append(stack.pop())
        stack.pop()  # Discard '('
    elif is_operator(char):
        while stack and stack[-1] != '(' and precedence(char) <= precedence(stack[-1]):
            postfix.append(stack.pop())
        stack.append(char)

while stack:
    postfix.append(stack.pop())

return ''.join(postfix)

def build_expression_tree(postfix): stack = []

for char in postfix:
    if char.isalnum():
        node = Node(char)
        stack.append(node)
    elif is_operator(char):
        right = stack.pop()
        left = stack.pop()
        node = Node(char)
        node.left = left
        node.right = right
        stack.append(node)

return stack.pop()

def inorder_traversal(root): if root is None: return

inorder_traversal(root.left)
print(root.value, end=' ')
inorder_traversal(root.right)

Example usage

expression = "a+bc-(d/e+fg)"

postfix = infix_to_postfix(expression) print("Postfix expression:", postfix)

root = build_expression_tree(postfix)

print("Inorder traversal of the expression tree:") inorder_traversal(root)

19.Program to find Height of a binary tree class Node: def init(self, data): self.right=None self.left=None self.data=data def height(root): if root is None: return 0 else: left=height(root.left) right=height(root.right) return 1+max(left, right)

root=Node(5) root.left=Node(3) root.right=Node(9) root.left.left=Node(4) root.left.right=Node(1) val=height(root) print("Height of tree =",val) 20.Program to calculate & display Product of all leaf nodes of binary tree class Node: def init(self, data): self.right=None self.left=None self.data=data def product(root): if root is None: return 0 else: if root.left is None and root.right is None: L.append(root.data) product(root.left) product(root.right) root=Node(5) root.left=Node(9) root.right=Node(4) root.left.left=Node(3) root.left.right=Node(5) L=[] p=1 product(root) for i in L: p=p*i print(p)

ANS: class Node: def __init__(self, data): self.right=None self.left=None self.data=data

def product(root): global p if root is None: return if root.left is None and root.right is None: L.append(root.data) product(root.left) product(root.right)

root=Node(5) root.left=Node(9) root.right=Node(4) root.left.left=Node(3) root.left.right=Node(5)

L=[] p=1 product(root) for i in L: p=p*i print(p)

Program to Find kth maximum and kth minimum value in a binary search tree

class Node: def _init_(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root is None: return

inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)

def find_kth_maximum(values, k): if k > len(values) or k < 1: return None

return values[-k]

def find_kth_minimum(values, k): if k > len(values) or k < 1: return None

return values[k - 1]

Example usage

BST

root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)

Find kth maximum and kth minimum

values = [] inorder_traversal(root, values)

k = 3 kth_maximum = find_kth_maximum(values, k) kth_minimum = find_kth_minimum(values, k)

print(f"{k}th maximum value: {kth_maximum}") print(f"{k}th minimum value: {kth_minimum}")

ANS:
class Node: def __init__(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root is None: return

inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)

def find_kth_maximum(values, k): if k > len(values) or k < 1: return None

return values[-k]

def find_kth_minimum(values, k): if k > len(values) or k < 1: return None

return values[k - 1]

Example usage

BST

root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)

Find kth maximum and kth minimum

values = [] inorder_traversal(root, values)

k = 3 kth_maximum = find_kth_maximum(values, k) kth_minimum = find_kth_minimum(values, k)

print(f"{k}th maximum value: {kth_maximum}") print(f"{k}th minimum value: {kth_minimum}")

Program to Convert BST to min-heap

class Node: def _init_(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root is None: return

inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)

def build_min_heap(values, root): if root is None: return None

root.value = values.pop(0)

root.left = build_min_heap(values, root.left)
root.right = build_min_heap(values, root.right)

return root

def convert_bst_to_min_heap(root): values = [] inorder_traversal(root, values)

return build_min_heap(values, root)

def print_inorder(root): if root is None: return

print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)

Example usage

BST

root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)

Convert BST to min-heap

converted_root = convert_bst_to_min_heap(root)

Print the inorder traversal of the converted min-heap

print("Inorder traversal of the converted min-heap:") print_inorder(converted_root)

ANS: class Node: def __init__(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root is None: return

inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)

def build_min_heap(values, root): if root is None: return None

root.value = values.pop(0)

root.left = build_min_heap(values, root.left)
root.right = build_min_heap(values, root.right)

return root

def convert_bst_to_min_heap(root): values = [] inorder_traversal(root, values)

return build_min_heap(values, root)

def print_inorder(root): if root is None: return

print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)

Example usage

BST

root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)

Convert BST to min-heap

converted_root = convert_bst_to_min_heap(root)

Print the inorder traversal of the converted min-heap

print("Inorder traversal of the converted min-heap:") print_inorder(converted_root)

Program to combine two binary search trees into a single tree

class Node: def _init_(self, value): self.value = value self.left = None self.right = None

def inorder_traversal(root, values): if root is None: return

inorder_traversal(root.left, values)
values.append(root.value)
inorder_traversal(root.right, values)

def create_bst_from_sorted(values, start, end): if start > end: return None

mid = (start + end) // 2
root = Node(values[mid])

root.left = create_bst_from_sorted(values, start, mid - 1)
root.right = create_bst_from_sorted(values, mid + 1, end)

return root

def combine_bsts(root1, root2): values1 = [] values2 = []

inorder_traversal(root1, values1)
inorder_traversal(root2, values2)

combined_values = sorted(values1 + values2)

return create_bst_from_sorted(combined_values, 0, len(combined_values) - 1)

def print_inorder(root): if root is None: return

print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)

Example usage

Tree 1

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

Tree 2

root2 = Node(7) root2.left = Node(6) root2.right = Node(8)

Combine the trees

combined_root = combine_bsts(root1, root2)

Print the combined tree

print("Inorder traversal of the combined tree:") print_inorder(combined_root)

ANS:class Node: def __init__(self, value): self.value = value self.left = None self.right = None

def merge_trees(root1, root2): if not root1: return root2 if not root2: return root1

if root1.value < root2.value:
    root1.right = merge_trees(root1.right, root2)
    return root1
else:
    root2.right = merge_trees(root2.right, root1)
    return root2

def print_inorder(root): if not root: return

print_inorder(root.left)
print(root.value, end=' ')
print_inorder(root.right)

Example usage

Tree 1

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

Tree 2

root2 = Node(7) root2.left = Node(6) root2.right = Node(8)

Combine the trees

combined_root = merge_trees(root1, root2)

Print the combined tree

print("Inorder traversal of the combined tree:") print_inorder(combined_root)

24.Program to Count number of nodes in a binary tree class Node: def init(self, data): self.left=None self.right=None self.data=data

def count(root): if root is None: return 0 else: return 1+count(root.left)+count(root.right)

root=Node(5) root.left=Node(2) root.right=Node(4) root.left.left=Node(5) root.left.right=Node(3) val=count(root) print("count = ",val)

ANS:class Node: def __init__(self, data): self.left = None self.right = None self.data = data

def count(root): if root is None: return 0 else: return 1 + count(root.left) + count(root.right)

root = Node(5) root.left = Node(2) root.right = Node(4) root.left.left = Node(5) root.left.right = Node(3) val = count(root) print("count =", val)

25.

Program to remove all nodes which don’t line in any path with sum >= K.

class Node: def _init_(self, value): self.value = value self.left = None self.right = None

def remove_nodes(root, k): if root is None: return None

root.left = remove_nodes(root.left, k)
root.right = remove_nodes(root.right, k)

if root.left is None and root.right is None:
    if root.value < k:
        return None

return root

def print_tree(root): if root is None: return

print_tree(root.left)
print(root.value, end=' ')
print_tree(root.right)

Example usage

root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7)

k = 6

print("Original tree:")

ANS: class Node: def __init__(self, value): self.value = value self.left = None self.right = None

def remove_nodes(root, k): if root is None: return None

root.left = remove_nodes(root.left, k)
root.right = remove_nodes(root.right, k)

if root.left is None and root.right is None:
    if root.value < k:
        return None

return root

def print_tree(root): if root is None: return

print_tree(root.left)
print(root.value, end=' ')
print_tree(root.right)

Example usage

root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7)

k = 6

print("Original tree:") print_tree(root)

root = remove_nodes(root, k)

print("\nModified tree:") print_tree(root)