What do you know about binary trees?

A binary tree is a data structure consisting of nodes, where each node has at most two children: left and right.

Key concepts:

• Root: The topmost node.
• Node: The basic element of the tree, containing data and references to child elements.
• Parent node: A node that has children.
• Child node: A node under a parent node.
• Leaf: A node with no children.
• Depth: The distance from the root to a node.
• Height: The maximum depth from the root to the deepest leaf.

Types of binary trees:

• Full Binary Tree: Each node has either 0 or 2 children.
• Perfect Binary Tree: All internal nodes have exactly 2 children, and all leaves are at the same depth.
• Balanced Binary Tree: The difference in depth between the left and right subtrees for each node is limited by a small constant (e.g., 1, as in AVL trees).

Applications:

• Binary Search Trees
• Heaps
• Huffman Trees
• Expressions

Example of a node in Python:

class Node:
    def __init__(self, data):
        self.data = data  # Node data
        self.left = None  # Left child
        self.right = None # Right child

Tree traversal methods:

• Pre-order: Root -> Left subtree -> Right subtree.
• In-order: Left subtree -> Root -> Right subtree (commonly used in BST to get sorted data).
• Post-order: Left subtree -> Right subtree -> Root.
• Level-order: Level by level, from left to right.

Operation complexities (for balanced trees):

Operation	Average case	Worst case
Insertion	O(log n)	O(n)
Search	O(log n)	O(n)
Deletion	O(log n)	O(n)