TREES AND BINARY TREES
======================
A tree is a hierarchical data structure. Root is the topmost node.
Each node has at most one parent and zero or more children.
Leaf nodes have no children.

--- Binary Tree Node ---
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Build a sample tree:
#        1
#       / \
#      2   3
#     / \   \
#    4   5   6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

--- Tree Traversals ---
# Inorder (Left, Root, Right) — gives sorted output for BST
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Preorder (Root, Left, Right) — used to copy the tree
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Postorder (Left, Right, Root) — used to delete the tree
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Level Order (BFS)
from collections import deque
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

print(inorder(root))     # [4, 2, 5, 1, 3, 6]
print(preorder(root))    # [1, 2, 4, 5, 3, 6]
print(postorder(root))   # [4, 5, 2, 6, 3, 1]
print(level_order(root)) # [1, 2, 3, 4, 5, 6]

--- Tree Height ---
def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

print(height(root))  # Output: 3

--- Count Nodes ---
def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

--- Binary Search Tree (BST) ---
Left child < Parent < Right child.
Insert, Search, Delete: O(log n) average, O(n) worst (skewed).

# Insert into BST
def bst_insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root

# Search in BST
def bst_search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return bst_search(root.left, val)
    return bst_search(root.right, val)

# Delete from BST
def bst_delete(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = bst_delete(root.left, val)
    elif val > root.val:
        root.right = bst_delete(root.right, val)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Find inorder successor (smallest in right subtree)
        curr = root.right
        while curr.left:
            curr = curr.left
        root.val = curr.val
        root.right = bst_delete(root.right, curr.val)
    return root

bst = None
for v in [5, 3, 7, 1, 4, 6, 8]:
    bst = bst_insert(bst, v)
print(inorder(bst))  # [1, 3, 4, 5, 6, 7, 8]

--- Check if Balanced ---
A tree is balanced if height difference of left and right subtrees is at most 1 for every node.

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left  = check(node.left)
        right = check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return check(root) != -1

--- Lowest Common Ancestor (LCA) ---
Find the lowest node that has both p and q as descendants.

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root  # p and q on different sides
    return left or right

--- Level Order by Levels ---
Return nodes grouped by level.

def level_order_levels(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

print(level_order_levels(root))
# Output: [[1], [2, 3], [4, 5, 6]]

--- Diameter of Binary Tree ---
Longest path between any two nodes (path may not pass through root).

def diameter(root):
    max_d = [0]
    def depth(node):
        if not node:
            return 0
        left  = depth(node.left)
        right = depth(node.right)
        max_d[0] = max(max_d[0], left + right)
        return 1 + max(left, right)
    depth(root)
    return max_d[0]

--- Invert Binary Tree ---
Mirror the tree — swap left and right children of every node.

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

--- AVL Tree (Self-Balancing BST) ---
Keeps height O(log n) by rotating after every insert/delete.
Balance factor = height(left) - height(right). Must be -1, 0, or 1.

def get_height(node):
    return node.height if node else 0

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

# Right rotation
def rotate_right(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x

# Left rotation
def rotate_left(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y