Introduction
A special binary tree is a tree which can only have zero or two child nodes. It can be traversed through by three methods: Inorder traversal, Preorder traversal and Postorder traversal.
In preorder traversal, we start with the root node, then move to the left subtree and then to the right subtree, doing the same thing.
Let’s discuss how to construct a special tree when a preorder traversal is given.
Problem Statement
In this problem, we have been given two arrays. The first, prtv[], represents the preorder traversal of a special binary tree. The second array, prLN[], possesses only two values, L and N, representing a leaf node and a non-leaf node, respectively. We have to write a function that can create a special binary tree from the given arrays.
Sample Examples
Input:
prtv[] = {5, 10, 20, 25, 15, 30, 35},
prLN[] = {'N', 'N', 'L', 'L', 'N', 'L', ‘L’}
Output:
The final tree:
5
/ \
10 15
/ \ / \
20 25 30 35Must Recommended Topic, Binary Tree Postorder Traversal.
Brute Force Approach
As the prtv[] array represents the preorder traversal, the first element will always be the root of the tree. If the left subtree is empty, then the right subtree will also be empty, and so the node will be a non-leaf or ‘N’ entry in the prLN[] array. So, the solution is just that one node that we have to create. If the node is not childless, we can recursively call both the left and right subtrees and link them to the root node. This would give the solution.
Steps of Algorithm
- The pvrt[] array represents the preorder traversal so that the first element would be the root of the special binary tree. We make the root node and insert the value in it.
- If the corresponding value in prLN[] for the indexed node is N, we recursively add the child nodes into the tree.
- This goes on until the index goes through the entire array, then it returns the created special binary tree. This is the answer.
Implementation in C++
#include<bits/stdc++.h>
struct node {
int data;
struct node *left;
struct node *right;
};
// Function to create a new node
struct node* newNode (int data) {
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Recursive function to create a special binary tree
struct node *constructTreeUtil(int prtv[], char prLN[], int *idx_ptr, int n) {
int idx = *idx_ptr; // store the current value of index in prtv[]
if (idx == n)
return NULL;
struct node *temp = newNode(prtv[idx]);
(*idx_ptr)++;
if(prLN[idx] == 'N') {
temp->left = constructTreeUtil(prtv, prLN, idx_ptr, n);
temp->right = constructTreeUtil(prtv, prLN, idx_ptr, n);
}
return temp;
}
// A wrapper over constructTreeUtil()
struct node *constructTree(int prtv[], char prLN[], int n) {
int idx = 0;
return constructTreeUtil(prtv, prLN, &idx, n);
}
void disInorder(struct node* node) {
if(node == NULL)
return;
disInorder(node->left);
printf("%d ", node->data);
disInorder(node->right);
}
int main() {
struct node *root = NULL;
int prtv[] = {5, 10, 20, 25, 15, 30, 35};
char prLN[] = {'N', 'N', 'L', 'L', 'N', 'L', 'L'};
int n = sizeof(prtv)/sizeof(prtv[0]);
root = constructTree(prtv, prLN, n);
printf("Created special binary tree in Inorder Traversal: \n");
disInorder(root);
return 0;
}
Output:
Created special binary tree in Inorder Traversal:
20 10 25 5 30 15 35
Complexity Analysis
Time Complexity: O(N)
Explanation: The code will run for every new node, so the time complexity is O(N).
Space Complexity: O(N)
Explanation: In this approach, space is needed for every node, so the space complexity is O(N).
34+ registered 
