🔍 Search in Binary Tree

Follow Me

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)