Searching in a Binary Tree involves checking whether a value exists in the tree or not.
There are two common types of binary trees:
✅ Binary Tree (BT) → Any node can be anywhere
✅ Binary Search Tree (BST) → Left < Root < Right (Sorted structure)
🔹 1. Search in a General Binary Tree (Recursive DFS)
def search_bt(root, key):
if root is None:
return False
if root.data == key:
return True
return search_bt(root.left, key) or search_bt(root.right, key)
🔹 2. Search in Binary Tree using Level Order (BFS)
from collections import deque
def search_bt_level_order(root, key):
if root is None:
return False
queue = deque([root])
while queue:
node = queue.popleft()
if node.data == key:
return True
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return False
🔹 3. Search in Binary Search Tree (BST) (Efficient - O(log n) for balanced trees)
def search_bst(root, key):
if root is None or root.data == key:
return root is not None
if key < root.data:
return search_bst(root.left, key)
else:
return search_bst(root.right, key)
✅ Example Binary Tree Code for Testing
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Create Binary Tree
root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)
# Search
print(search_bt(root, 7)) # True
print(search_bt_level_order(root, 99)) # False
print(search_bst(root, 20)) # True (Only use for BST)
No comments:
Post a Comment