Maximum branching factor: max children of any node
Average branching factor: total children / number of non-leaf nodes
Effective branching factor: N^(1/d) where N = nodes explored, d = depth

1        A           (3 children)
2      / | \
3     B  C  D        (B: 2 children, C: 0, D: 1)
4    / \     \
5   E   F    G       (all leaves: 0 children)

1class TreeNode:
2    def __init__(self, value, children=None):
3        self.value = value
4        self.children = children or []
5
6def average_branching_factor(root):
7    """Calculate the average branching factor of a tree."""
8    total_children = 0
9    non_leaf_count = 0
10
11    def traverse(node):
12        nonlocal total_children, non_leaf_count
13        if node.children:  # Non-leaf node
14            total_children += len(node.children)
15            non_leaf_count += 1
16        for child in node.children:
17            traverse(child)
18
19    traverse(root)
20    return total_children / non_leaf_count if non_leaf_count > 0 else 0
21
22# Build the example tree
23root = TreeNode('A', [
24    TreeNode('B', [TreeNode('E'), TreeNode('F')]),
25    TreeNode('C'),
26    TreeNode('D', [TreeNode('G')])
27])
28
29print(f"Average branching factor: {average_branching_factor(root)}")
30# Average branching factor: 2.0

1def max_branching_factor(root):
2    """Find the maximum number of children any node has."""
3    max_children = 0
4
5    def traverse(node):
6        nonlocal max_children
7        max_children = max(max_children, len(node.children))
8        for child in node.children:
9            traverse(child)
10
11    traverse(root)
12    return max_children
13
14print(f"Max branching factor: {max_branching_factor(root)}")
15# Max branching factor: 3

N = 1 + b* + b*^2 + ... + b*^d

1def effective_branching_factor(nodes_explored, depth, tolerance=1e-6):
2    """Binary search for the effective branching factor b*."""
3    lo, hi = 1.0, float(nodes_explored)
4
5    while hi - lo > tolerance:
6        mid = (lo + hi) / 2
7        # Sum of geometric series: (b^(d+1) - 1) / (b - 1)
8        if mid == 1.0:
9            total = depth + 1
10        else:
11            total = (mid ** (depth + 1) - 1) / (mid - 1)
12
13        if total < nodes_explored:
14            lo = mid
15        else:
16            hi = mid
17
18    return (lo + hi) / 2
19
20# BFS explored 55 nodes at depth 3
21b_star = effective_branching_factor(55, 3)
22print(f"Effective branching factor: {b_star:.2f}")
23# Effective branching factor: 3.00 (perfect for b=3 tree)
24
25# A* explored 20 nodes at depth 3 (more efficient)
26b_star = effective_branching_factor(20, 3)
27print(f"Effective branching factor: {b_star:.2f}")
28# Effective branching factor: 2.15 (better than BFS)

1def branching_factor_from_counts(total_nodes, leaf_nodes):
2    """Calculate average branching factor from node counts."""
3    non_leaf = total_nodes - leaf_nodes
4    edges = total_nodes - 1  # Every node except root has one incoming edge
5
6    if non_leaf == 0:
7        return 0  # Only root, no branches
8
9    return edges / non_leaf
10
11# Tree with 7 nodes, 4 leaves
12bf = branching_factor_from_counts(7, 4)
13print(f"Average branching factor: {bf:.2f}")
14# Average branching factor: 2.0

1from collections import deque
2
3def branching_factor_bfs(root):
4    """Compute branching factor using BFS traversal."""
5    if not root:
6        return 0
7
8    queue = deque([root])
9    total_children = 0
10    non_leaf_count = 0
11    node_count = 0
12    depth_nodes = {}
13
14    depth = 0
15    queue.append(None)  # Level marker
16
17    while queue:
18        node = queue.popleft()
19
20        if node is None:
21            if queue:
22                depth += 1
23                queue.append(None)
24            continue
25
26        node_count += 1
27        if node.children:
28            non_leaf_count += 1
29            total_children += len(node.children)
30            for child in node.children:
31                queue.append(child)
32
33    avg_bf = total_children / non_leaf_count if non_leaf_count > 0 else 0
34    return {
35        'average': avg_bf,
36        'total_nodes': node_count,
37        'non_leaf_nodes': non_leaf_count,
38        'depth': depth
39    }
40
41stats = branching_factor_bfs(root)
42print(f"Average: {stats['average']:.2f}, Nodes: {stats['total_nodes']}, Depth: {stats['depth']}")

1Time complexity of tree search:  O(b^d)
2Space complexity of BFS:         O(b^d)
3Space complexity of DFS:         O(b * d)
4
5Where b = branching factor, d = depth