Binary Trees

1 min read•1 page

A Binary Tree is a tree structure where every node has at most two children, referred to as the left child and the right child.

BinaryNode(key, value):

1. Key: The value used to sort and search the tree. 2. Left Child: Node with key less than parent key (in Binary Search Trees). 3. Right Child: Node with key greater than parent key.

python

1class BinaryNode:
2    def __init__(self, key, value=None):
3        self.key = key         # Search key / index value
4        self.value = value     # Associated data payload
5        self.left = None       # Reference to left child (BinaryNode)
6        self.right = None      # Reference to right child (BinaryNode)

1 min read•1 page

To build a Binary Search Tree (BST), we insert keys recursively. At every node, we check if the new key is smaller (routing it left) or larger (routing it right), until an empty slot is found.

Insert(node, key):

1. Key < Node: Recurse into the left subtree. 2. Key > Node: Recurse into the right subtree. 3. Base Case: Create a new node when a null link is encountered.

python

1def insert(node, key, value=None) -> BinaryNode:
2    # If the tree is empty, return a new node
3    if node is None:
4        return BinaryNode(key, value)
5        
6    # Otherwise, recur down the tree
7    if key < node.key:
8        node.left = insert(node.left, key, value)
9    elif key > node.key:
10        node.right = insert(node.right, key, value)
11        
12    return node

Key to Insert

35.00

2 min read•1 page

Binary search trees allow fast lookup operations. At each node, we compare the target key. Since we discard half the remaining tree at each comparison, the search takes O(log N) time.

Search(node, target_key):

1. Equal: Target found, return node. 2. Smaller: Search left subtree recursively. 3. Larger: Search right subtree recursively.

python

1def search(node, target_key) -> BinaryNode:
2    # Base Cases: root is null or key is present at root
3    if node is None or node.key == target_key:
4        return node
5        
6    # Target is smaller than root's key
7    if target_key < node.key:
8        return search(node.left, target_key)
9        
10    # Target is greater than root's key
11    return search(node.right, target_key)

Target Key to Search

40.00

2 min read•1 page

Traversal means visiting all nodes of a tree in a specific order. For binary trees, we have three standard depth-first search (DFS) traversal orderings.

Traverse(node, order):

1. Pre-order (NLR): Visit Node, then Left, then Right. 2. In-order (LNR): Visit Left, then Node, then Right. Output is sorted for BSTs! 3. Post-order (LRN): Visit Left, then Right, then Node. Used to delete trees.

python

1def traverse(node, order_type="inorder"):
2    if node is None:
3        return
4        
5    if order_type == "preorder":
6        print(node.key)          # Visit Root
7        traverse(node.left)       # Left child
8        traverse(node.right)      # Right child
9        
10    elif order_type == "inorder":
11        traverse(node.left)       # Left child
12        print(node.key)          # Visit Root
13        traverse(node.right)      # Right child
14        
15    elif order_type == "postorder":
16        traverse(node.left)       # Left child
17        traverse(node.right)      # Right child
18        print(node.key)          # Visit Root

Traversal Type (0: Pre, 1: In, 2: Post)

0.00

Traversal Progress Step

0.00