fork download
copy 
  1. # ============================================
  2. # Binary Search Tree (BST) - Full Implementation
  3. # ============================================
  4.  
  5. class Node:
  6.     def __init__(self, key):
  7.         self.key = key
  8.         self.left = None
  9.         self.right = None
  10.  
  11.  
  12. class BST:
  13.     def __init__(self):
  14.         self.root = None
  15.  
  16.     # --------------------------------------
  17.     # INSERT
  18.     # --------------------------------------
  19.     def insert(self, key):
  20.         self.root = self._insert_recursive(self.root, key)
  21.  
  22.     def _insert_recursive(self, node, key):
  23.         if node is None:
  24.             return Node(key)
  25.         if key < node.key:
  26.             node.left = self._insert_recursive(node.left, key)
  27.         else:
  28.             node.right = self._insert_recursive(node.right, key)
  29.         return node
  30.     # --------------------------------------
  31.     # HEIGHT OF TREE
  32.     # --------------------------------------
  33.     def height(self, node=None):
  34.         if node is None:
  35.             node = self.root
  36.         return self._height_recursive(node)
  37.     # Private helper used for recursion
  38.     def _height_recursive(self, node):
  39.         if node is None:
  40.             return -1
  41.         left_h = self._height_recursive(node.left)
  42.         right_h = self._height_recursive(node.right)
  43.         return 1 + max(left_h, right_h)
  44.  
  45.  
  46.  
  47.     # --------------------------------------
  48.     # SEARCH
  49.     # --------------------------------------
  50.     def search(self, key):
  51.         return self._search_recursive(self.root, key)
  52.  
  53.     def _search_recursive(self, node, key):
  54.         if node is None or node.key == key:
  55.             return node
  56.         if key < node.key:
  57.             return self._search_recursive(node.left, key)
  58.         else:
  59.             return self._search_recursive(node.right, key)
  60.  
  61.     # --------------------------------------
  62.     # MINIMUM
  63.     # --------------------------------------
  64.     def find_min(self, node=None):
  65.         if node is None:
  66.             node = self.root
  67.         while node.left:
  68.             node = node.left
  69.         return node
  70.  
  71.     # --------------------------------------
  72.     # MAXIMUM
  73.     # --------------------------------------
  74.     def find_max(self, node=None):
  75.         if node is None:
  76.             node = self.root
  77.         while node.right:
  78.             node = node.right
  79.         return node
  80.  
  81.     # --------------------------------------
  82.     # INORDER TRAVERSAL (sorted)
  83.     # --------------------------------------
  84.     def inorder(self):
  85.         result = []
  86.         self._inorder_recursive(self.root, result)
  87.         return result
  88.  
  89.     def _inorder_recursive(self, node, result):
  90.         if node:
  91.             self._inorder_recursive(node.left, result)
  92.             result.append(node.key)
  93.             self._inorder_recursive(node.right, result)
  94.  
  95.     # --------------------------------------
  96.     # PREORDER TRAVERSAL
  97.     # --------------------------------------
  98.     def preorder(self):
  99.         result = []
  100.         self._preorder_recursive(self.root, result)
  101.         return result
  102.  
  103.     def _preorder_recursive(self, node, result):
  104.         if node:
  105.             result.append(node.key)
  106.             self._preorder_recursive(node.left, result)
  107.             self._preorder_recursive(node.right, result)
  108.  
  109.     # --------------------------------------
  110.     # POSTORDER TRAVERSAL
  111.     # --------------------------------------
  112.     def postorder(self):
  113.         result = []
  114.         self._postorder_recursive(self.root, result)
  115.         return result
  116.  
  117.     def _postorder_recursive(self, node, result):
  118.         if node:
  119.             self._postorder_recursive(node.left, result)
  120.             self._postorder_recursive(node.right, result)
  121.             result.append(node.key)
  122.  
  123.     # --------------------------------------
  124.     # DELETE NODE
  125.     # --------------------------------------
  126.     def delete(self, key):
  127.         self.root = self._delete_recursive(self.root, key)
  128.  
  129.     def _delete_recursive(self, node, key):
  130.         if node is None:
  131.             return node
  132.  
  133.         if key < node.key:
  134.             node.left = self._delete_recursive(node.left, key)
  135.         elif key > node.key:
  136.             node.right = self._delete_recursive(node.right, key)
  137.         else:
  138.             # Case 1: No child
  139.             if node.left is None and node.right is None:
  140.                 return None
  141.             # Case 2: One child
  142.             elif node.left is None:
  143.                 return node.right
  144.             elif node.right is None:
  145.                 return node.left
  146.             # Case 3: Two children
  147.             else:
  148.                 successor = self.find_min(node.right)
  149.                 node.key = successor.key
  150.                 node.right = self._delete_recursive(node.right, successor.key)
  151.  
  152.         return node
  153.  
  154.       # --------------------------------------
  155.     # COUNT NODES
  156.     # --------------------------------------
  157.     def count_nodes(self, node=None):
  158.         if node is None:
  159.             node = self.root
  160.         if node is None:
  161.             return 0
  162.         return 1 + self.count_nodes(node.left) + self.count_nodes(node.right)
  163.  
  164.     # --------------------------------------
  165.     # VALIDATE BST
  166.     # --------------------------------------
  167.     def is_valid_bst(self):
  168.         return self._validate(self.root, float('-inf'), float('inf'))
  169.  
  170.     def _validate(self, node, low, high):
  171.         if node is None:
  172.             return True
  173.         if not (low < node.key < high):
  174.             return False
  175.         return (self._validate(node.left, low, node.key) and
  176.                 self._validate(node.right, node.key, high))
  177.  
  178.     # --------------------------------------
  179.     # SUCCESSOR
  180.     # --------------------------------------
  181.     def successor(self, key):
  182.         node = self.search(key)
  183.         if node is None:
  184.             return None
  185.  
  186.         # Case 1: right subtree exists
  187.         if node.right:
  188.             return self.find_min(node.right)
  189.  
  190.         # Case 2: climb ancestors
  191.         succ = None
  192.         cur = self.root
  193.         while cur:
  194.             if key < cur.key:
  195.                 succ = cur
  196.                 cur = cur.left
  197.             elif key > cur.key:
  198.                 cur = cur.right
  199.             else:
  200.                 break
  201.         return succ
  202.  
  203.     # --------------------------------------
  204.     # PREDECESSOR
  205.     # --------------------------------------
  206.     def predecessor(self, key):
  207.         node = self.search(key)
  208.         if node is None:
  209.             return None
  210.  
  211.         # Case 1: left subtree exists
  212.         if node.left:
  213.             return self.find_max(node.left)
  214.  
  215.         # Case 2: climb ancestors
  216.         pred = None
  217.         cur = self.root
  218.         while cur:
  219.             if key > cur.key:
  220.                 pred = cur
  221.                 cur = cur.right
  222.             elif key < cur.key:
  223.                 cur = cur.left
  224.             else:
  225.                 break
  226.         return pred
  227.  
  228. tree = BST()
  229.  
  230. for x in [50, 30, 70, 20, 40, 60, 80, 100, 42,10,55]:
  231.     tree.insert(x)
  232.  
  233. print("Inorder:", tree.inorder())
  234. print("Postorder:", tree.postorder())
  235. print("Postorder:", tree.preorder())
  236. print("Search 40:", tree.search(40))
  237. print("Min:", tree.find_min().key)
  238. print("Max:", tree.find_max().key)
  239. print("Height:", tree.height())
  240. print("Successor of 50:", tree.successor(50).key)
  241. print("Predecessor of 50:", tree.predecessor(50).key)
  242.  
  243. tree.delete(70)
  244. print("After deletion:", tree.inorder())
  245.  
Success #stdin #stdout 0.11s 14088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder: [10, 20, 30, 40, 42, 50, 55, 60, 70, 80, 100]
Postorder: [10, 20, 42, 40, 30, 55, 60, 100, 80, 70, 50]
Postorder: [50, 30, 20, 10, 40, 42, 70, 60, 55, 80, 100]
Search 40: <__main__.Node object at 0x14ac76119c10>
Min: 10
Max: 100
Height: 3
Successor of 50: 55
Predecessor of 50: 42
After deletion: [10, 20, 30, 40, 42, 50, 55, 60, 80, 100]
https://ideone.com/tb3ufm
language:
Python 3 (python  3.12)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!