Binary Tree Expansion

Problem Statement

Binary Tree Expansion The problem focuses on a data structure called binary tree. A node of a binary tree has an ID (an integer value) and pointers to two other nodes, called the left subtree and the right subtree . If the left subtree or right subtree does not exist, its corresponding pointer value is NULL. For example, the figure below shows a binary tree consisting of six nodes. Here, node 3 does not have a right subtree, and nodes 4, 5 and 6 are leaves - they do not have any subtree. Structure Definition struct tree { int x; struct tree * l; struct tree * r; }; Attribute x holds the node's ID, whereas attributes l and r hold the left and right subtree , respectively. Your task is to expand the tree by replacing every leaf with a new node whose subtrees are both leaves. The IDs of each new node and its two leaves should correspond to the ID of the leaf they replaced. Function Description struct tree * solution(struct tree * T); The function should return the expanded version of the