Binary Tree Creation from Array

Understanding the Concept

A binary tree is a hierarchical data structure in which each node has at most two children: the left child and the right child. This tutorial will explain how to create a binary tree from an array using a 1-indexed approach.

In a 1-indexed array, the position of the root node is at index 1. The left child of the node at index x is located at 2x, and the right child is at 2x + 1. Using this logic, we can recursively construct a binary tree.

Algorithm Overview

1. Start with an array of elements (e.g., [3, 6, 9, 12, 5, 3, 4, 8]).
2. Create a recursive function to construct nodes based on their positions in the array.
3. Assign the root node from the first element and recursively define its left and right children.
4. Stop recursion when the index exceeds the length of the array.

Python Code Implementation

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

def create_binary_tree(array, i, n):
    """
    Recursive function to create a binary tree from a 1-indexed array.
    :param array: List[int] - The array representation of the binary tree.
    :param i: int - The current index in the array (1-indexed).
    :param n: int - The total number of elements + 1 (1-indexed).
    :return: TreeNode - The root of the binary tree.
    """
    # Base case: Check if index is within bounds
    if i < n:
        # Create a node for the current index
        root = TreeNode(array[i - 1])
        # Recursively create left and right subtrees
        root.left = create_binary_tree(array, 2 * i, n)
        root.right = create_binary_tree(array, 2 * i + 1, n)
        return root
    return None

# Example Usage
array = [3, 6, 9, 12, 5, 3, 4, 8]  # Array representation of the tree
n = len(array) + 1  # Convert to 1-indexed array length
root = create_binary_tree(array, 1, n)

# Function to visualize the tree (optional)
def print_tree(node, level=0, side="root"):
    if node:
        print(" " * (level * 4) + f"({side}) -> {node.value}")
        print_tree(node.left, level + 1, "L")
        print_tree(node.right, level + 1, "R")

# Print the tree structure
print_tree(root)

The code constructs a binary tree from the given array, following the 1-indexed approach. The root node is at index 1, and its children are calculated as explained above.