Binary Tree Cheat Sheet

Here’s a cheat sheet for working with binary trees in Python:

Binary Tree Node Definition

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Tree Traversals

Inorder Traversal:

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)

Preorder Traversal:

def preorder_traversal(node):
    if node:
        print(node.value)
        preorder_traversal(node.left)
        preorder_traversal(node.right)

Postorder Traversal:

def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value)

Level Order Traversal (BFS)

from collections import deque

def level_order_traversal(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.value)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

Height of Binary Tree

def height_of_tree(node):
    if not node:
        return 0

    left_height = height_of_tree(node.left)
    right_height = height_of_tree(node.right)

    return 1 + max(left_height, right_height)

Check if Binary Tree is Balanced

def is_balanced(root):
    if not root:
        return True

    left_height = height_of_tree(root.left)
    right_height = height_of_tree(root.right)

    if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
        return True

    return False

Binary Search Tree (BST) Operations

Insertion:

def insert_bst(root, value):
    if not root:
        return TreeNode(value)

    if value < root.value:
        root.left = insert_bst(root.left, value)
    else:
        root.right = insert_bst(root.right, value)

    return root

Search in BST:

def search_bst(root, value):
    if not root or root.value == value:
        return root

    if value < root.value:
        return search_bst(root.left, value)
    else:
        return search_bst(root.right, value)

Lowest Common Ancestor (LCA) in BST

def lowest_common_ancestor(root, p, q):
    if not root:
        return None

    if p.value < root.value and q.value < root.value:
        return lowest_common_ancestor(root.left, p, q)
    elif p.value > root.value and q.value > root.value:
        return lowest_common_ancestor(root.right, p, q)
    else:
        return root

These snippets cover basic binary tree operations. For more advanced algorithms and concepts related to binary trees, refer to specialized resources and textbooks.