Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What type of data structures are stacks?
4.2.
What is the difference between inorder traversal and preorder traversal?
4.3.
What are the limitations of the stack?
5.
Conclusion
Last Updated: Mar 27, 2024

Construct a special tree from given preorder traversal

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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  35

Must 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.

Source

Steps of Algorithm

  1. 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.
  2. If the corresponding value in prLN[] for the indexed node is N, we recursively add the child nodes into the tree.
  3. 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

This approach is pretty similar to the last one. We just use stacks and their properties to optimise the algorithm. We take the tree’s root from the first element of the pvrt[] array. We check each node for children and push them into the stack.

Steps of Algorithm

  1. 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.
  2. We traverse the pvrt[] array.
    1. If the indexed node is not a leaf node, push its value into the stack.
    2. We check the left of the stack’s top. We can add the indexed node on the left if it is null. If it is not and the right is null, add the node on the right.
    3. If both the left and right are not null, that means the node has both left and right children. Pop these nodes out until we get to the leaf nodes.
  3. In the end, we can return the root of the created special binary tree.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
    node(int x) {
        data = x;
        left = right = NULL;
    }
};

struct node* constructTree(int prtv[], char prLN[], int n) {
    stack<node*> st;

    node* root = new node(prtv[0]);
    if (prLN[0] != 'L')
        st.push(root);

    for (int i = 1; i < n; i++) {
        node* temp = new node(prtv[i]);

        if (!st.top()->left) {
            st.top()->left = temp;

            if (prLN[i] != 'L')
                st.push(temp);
        }

        else if (!st.top()->right) {
            st.top()->right = temp;
            if (prLN[i] != 'L')
                st.push(temp);
        }

        else {
            while (st.top()->left && st.top()->right)
                st.pop();
            st.top()->right = temp;
            if (prLN[i] != 'L')
                st.push(temp);
        }
    }
    return root;
}

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).

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

What type of data structures are stacks?

A stack is a linear data structure that operates on the Last In First Out principle (LIFO).

This indicates that the last thing added to the stack is deleted first. The stack data structure can be compared to a stack of plates stacked on top of each other.

What is the difference between inorder traversal and preorder traversal?

In Inorder, you travel from the left subtree to the root, then to the right subtree. While for Preorder traversal, you move from the root to the left subtree, then to the right subtree. Their values would be the same if the tree had only right children.

What are the limitations of the stack?

The memory size available in the stack is quite restricted. Stack overflow can occur if you create too many objects on the stack. It is not feasible to have random access. Variable storage will be overwritten, resulting in unpredictable behaviour by the program.

Conclusion

In conclusion, we discussed different approaches to construct a special binary tree from a given preorder traversal. For every approach, we discussed algorithms and complexities. We eventually saw how each of the methods are different from the others.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Constructing a Binary Tree from two Traversal Sequences
Next article
Construct a Complete Binary Tree from given Array in Level Order Fashion
Live masterclass