Binary Trees: Structure and Traversal

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child.

Tree Terminology

• Root: The topmost node
• Parent: A node that has children
• Leaf: A node with no children
• Height: The longest path from root to a leaf
• Depth: Distance from the root to a node

Binary Tree Node

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

Tree Traversals

There are three main ways to traverse a binary tree:

1. Inorder Traversal (Left, Root, Right)

Visits nodes in ascending order for a Binary Search Tree.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

For a BST with values [1, 2, 3, 4, 5], inorder gives: 1, 2, 3, 4, 5

2. Preorder Traversal (Root, Left, Right)

Useful for creating a copy of the tree.

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

3. Postorder Traversal (Left, Right, Root)

Useful for deleting a tree or evaluating expressions.

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

Level Order Traversal (BFS)

Visits nodes level by level using a queue.

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

Time and Space Complexity

Operation	Average	Worst
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Space complexity for traversals: O(h) where h is the height

Common Tree Problems

1. Find the height of a tree
2. Check if a tree is balanced
3. Find the lowest common ancestor
4. Serialize and deserialize a tree
5. Convert sorted array to BST

Conclusion

Binary trees are fundamental data structures that form the basis for more complex structures like heaps, BSTs, and balanced trees. Understanding traversal methods is essential for solving tree-related problems.