Simple Expression Transformer: AST Manipulation in Go

This challenge focuses on manipulating the Abstract Syntax Tree (AST) of a simple arithmetic expression language. You'll be provided with a basic AST representation and tasked with writing a Go program that traverses this tree and modifies it to replace a specific operator with another. This exercise demonstrates fundamental AST manipulation techniques, crucial for compilers, interpreters, and code transformation tools.

Problem Description

You are given a simplified AST representation for arithmetic expressions. The AST consists of nodes representing either numbers or binary operators. Each operator node has a left child, a right child, and an operator symbol (a string). Your task is to write a Go function that takes an AST root node and an operator symbol as input. The function should traverse the AST and replace all occurrences of the specified operator symbol with a new operator symbol.

Key Requirements:

• AST Structure: The AST is represented by a Node struct with fields Value (float64 if it's a number, nil otherwise), Left (*Node), Right (*Node), and Operator (string).
• Operator Replacement: The function must recursively traverse the AST. When it encounters an operator node with the target operator symbol, it should update the Operator field of that node to the new operator symbol.
• Immutability (Important): The function should not modify the original AST in place. Instead, it should create and return a new AST with the modifications. This is crucial for maintaining the integrity of the original code.
• Error Handling: If the input root is nil, return nil.

Expected Behavior:

The function should return a new AST root node with the specified operator replaced throughout the tree. The structure of the AST (number nodes and operator placement) should remain unchanged, except for the operator symbols.

Edge Cases to Consider:

• Empty AST (root is nil).
• AST containing only numbers.
• Operator symbol not found in the AST.
• Deeply nested ASTs.

Examples

Example 1:

Input:
root: &Node{Operator: "+", Left: &Node{Value: 1.0}, Right: &Node{Operator: "+", Left: &Node{Value: 2.0}, Right: &Node{Value: 3.0}}}
oldOperator: "+"
newOperator: "*"

Output:
&Node{Operator: "*", Left: &Node{Value: 1.0}, Right: &Node{Operator: "*", Left: &Node{Value: 2.0}, Right: &Node{Value: 3.0}}}
Explanation: All "+" operators have been replaced with "*" operators in the new AST.

Example 2:

Input:
root: &Node{Operator: "-", Left: &Node{Value: 5.0}, Right: &Node{Value: 2.0}}
oldOperator: "-"
newOperator: "+"

Output:
&Node{Operator: "+", Left: &Node{Value: 5.0}, Right: &Node{Value: 2.0}}
Explanation: The "-" operator has been replaced with "+" in the new AST.

Example 3: (Edge Case - Operator not found)

Input:
root: &Node{Operator: "+", Left: &Node{Value: 1.0}, Right: &Node{Value: 2.0}}
oldOperator: "*"
newOperator: "/"

Output:
&Node{Operator: "+", Left: &Node{Value: 1.0}, Right: &Node{Value: 2.0}}
Explanation: Since "*" is not present, the AST remains unchanged.

Constraints

• The AST will only contain binary operators (+, -, *, /).
• The input AST will be well-formed (no cycles, valid structure).
• The oldOperator will always be a valid operator present in the AST or not present at all.
• The newOperator can be any string.
• The function must be efficient enough to handle ASTs with up to 100 nodes without significant performance degradation.

Notes

• Consider using recursion to traverse the AST.
• Remember to create a new AST instead of modifying the original. This will likely involve creating new Node instances during the traversal.
• Think about how to handle the base case of the recursion (when you reach a number node).
• The Node struct is defined below for your convenience. You do not need to define it.

type Node struct {
	Value    float64
	Left     *Node
	Right    *Node
	Operator string
}