• Introduction
• What is a Tree?
• Properties:
• What is a Binary Tree?
• Types of Binary Trees:
• Binary Tree Representation in Python
• Binary Tree Traversals
• 1. Inorder Traversal (Left, Root, Right)
• 2. Preorder Traversal (Root, Left, Right)
• 3. Postorder Traversal (Left, Right, Root)
• 4. Level Order Traversal of Trees
• Why Traversals Matter
• Important Properties
• Binary Tree Properties Table
• Binary Tree Cheat Sheet (Quick Reference)
• Node Types
• Traversal Orders
• Formulas
• Time Complexities
• Special Trees
• Traversal Patterns
• Common Binary Tree “Patterns” for LeetCode

Introduction

This blog post aims to help you store and remember properties of Trees and Binary Trees, and implement common traversal algorithms in Python.

What is a Tree?

A Tree is a hierarchical data structure consisting of nodes connected by edges. It has the following characteristics:

• Root: The topmost node of the tree.
• Parent & Child: Any node except the root has one parent; nodes connected below it are its children.
• Leaf Nodes: Nodes without children.
• Height/Depth: Number of edges on the longest path from the root to a leaf.
• Subtree: Any node and all its descendants form a subtree.

Properties:

1. A tree with $n$ nodes has $n-1$ edges.
2. There is exactly one path between any two nodes.
3. Trees are acyclic (no cycles).

What is a Binary Tree?

A Binary Tree is a type of tree where each node has at most two children:

• Left child
• Right child

Types of Binary Trees:

1. Full Binary Tree: Every node has 0 or 2 children.
2. Complete Binary Tree: All levels are fully filled except possibly the last, which is filled from left to right.
3. Perfect Binary Tree: All internal nodes have 2 children, and all leaves are at the same level.
4. Balanced Binary Tree: Difference between heights of left and right subtree ≤ 1 for every node.
5. Degenerate (Skewed) Tree: Each parent has only one child, effectively forming a linked list.

Binary Tree Representation in Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Example tree:
#        1
#       / \
#      2   3
#     / \
#    4   5

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

Binary Tree Traversals

Traversal is the process of visiting all nodes in a tree exactly once.

1. Inorder Traversal (Left, Root, Right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)

inorder(root)  # Output: 4 2 5 1 3

2. Preorder Traversal (Root, Left, Right)

def preorder(node):
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)

preorder(root)  # Output: 1 2 4 5 3

3. Postorder Traversal (Left, Right, Root)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=' ')

postorder(root)  # Output: 4 5 2 3 1

4. Level Order Traversal of Trees

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        dq = deque([root])
        traversed_tree = []
        if not root: return traversed_tree
        while dq:
            level = []
            for i in range(len(dq)):
                node = dq.popleft()
                level.append(node.val)
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
            traversed_tree.append(level)
        return traversed_tree

Why Traversals Matter

• Inorder of a BST returns sorted order → useful in search algorithms.
• Preorder can be used to clone a tree or serialize it.
• Postorder is useful for deleting or freeing nodes.

Important Properties

Perfect! Let’s make this super compact and interview-friendly. I’ll first create a table of properties and formulas, followed by a cheatsheet you can memorize quickly.

Binary Tree Properties Table

Binary Tree Cheat Sheet (Quick Reference)

Node Types

• Root: Top node
• Leaf: No children
• Internal Node: Has ≥1 child

Traversal Orders

• Inorder: Left → Root → Right → Sorted for BST
• Preorder: Root → Left → Right → Used in cloning/serialize
• Postorder: Left → Right → Root → Used in deletion
• Level Order (BFS): Level by level

Formulas

• Max nodes: 2^(h+1) - 1
• Min nodes: h + 1
• Max leaves: 2^h
• Height from nodes (perfect): h = log2(n+1) - 1

Time Complexities

Special Trees

• Full Binary Tree → 0 or 2 children
• Complete Binary Tree → All levels full except last, left to right
• Perfect Binary Tree → Full and all leaves same level
• Balanced → Height difference ≤1

Traversal Patterns

Include expected output examples (for easy recall):

Tree Example:

       1
      / \
     2   3
    / \
   4   5

Common Binary Tree “Patterns” for LeetCode

• Path sum (root-to-leaf sum)
• Diameter of a tree
• Symmetric / Mirror tree
• Lowest Common Ancestor (LCA)
• Serialize / Deserialize tree
• Flatten tree to linked list