binary-tree-implementation

implementing binary tree

tags: learning programming dsa

content

i have this code:

class Node:
	def __init__(self, key: int):
		self.key = key
		self.left = None
		self.right = None
 
class BinaryTree:
	def __init__(self):
		self.root: Node | None = None
	def insert(self, key: int):
		if self.root is None:
			self.root = Node(key)
			return
		self._insert(self, key, self.root)
	def _insert(self, key: int, current_node: Node | None):
		if current_node is None:
			return Node(key)
		if key < current_node.key:
			current_node.left = self._insert(key, current_node.left)
		else:
			current_node.right = self._insert(key, current_node.right)
		return current_node  # why?

my confusion is: why do i need to return current_node at the end?

• sort out the logic in _insert
  • base case: if current_node is none, we reach the bottom of the tree, we wanna create a new node and return
  • current_node is waiting for a new node to link to its child
    • so we have current_node.left = {waiting for a node}
  • because the caller (the previous current_node) is waiting for a node, we need to return current_node
    • otherwise, python implicitly return None
    • the previous node (who is waiting to a node as its child) will link None as its child
    • that means we’re losing the original structure one by one

up

down

reference