Table of contents
1.
Introduction 
1.1.
Example
2.
Recursive Approach
2.1.
Algorithm
2.2.
Dry Run 
2.3.
C++ Code
2.4.
Python Code
2.5.
Algorithm Complexity 
3.
Frequently Asked Questions
3.1.
What is the perfect binary tree?
3.2.
What is a subtree in a binary tree?
3.3.
What are the data members of a TreeNode class?
3.4.
What do you mean by preorder traversal?
3.5.
What do you mean by Inorder traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Construct A Perfect Binary Tree From A Preorder Traversal

Author Rishabh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

This blog will discuss the approach to solving the problem of constructing a perfect binary tree from a preorder traversal. Let’s first understand what a perfect binary tree is,

construct a perfect binary tree from a preorder traversal

A perfect binary tree is a binary tree in which all levels are completely filled with nodes, and all leaf nodes are at the same level. This means that every internal node has exactly two children.

For more information on binary trees, refer to this link.

Example

Input 

[15, 14, 18, 95, 47, 5, 479]

Output

 [18, 14, 95, 15, 5, 47, 479]

output perfect binary tree

Explanation

This code takes a vector of integers 'preorder' representing the preorder traversal of a binary tree and constructs a perfect binary tree using recursive calls to the buildTree function. The function builds the left and right subtrees of the current node recursively until the base case is reached. The constructed binary tree is then printed using the print function, which performs an inorder traversal of the tree.

Recursive Approach

This approach builds a perfect binary tree using a vector containing the preorder traversal of the tree and prints its inorder traversal. The tree is built recursively by dividing the vector into two halves and recursively building the left and right subtrees.

Algorithm

  1. The ‘buildTree’ function takes a vector ‘preorder’ and initializes two integers ‘start’ and ‘end’ as inputs and returns the root of the constructed perfect binary tree.
     
  2. If ‘start > end’, return NULL.
     
  3. Create a new node ‘root’ with the value ‘preorder[start]’.
     
  4. Compute the middle index `mid` as ‘(start + end) / 2’.
     
  5. Recursively build the left subtree using ‘buildTree(preorder, start + 1, mid)’ and assign it to ‘root->left’.
     
  6. Recursively build the right subtree using ‘buildTree(preorder, mid + 1, end)’ and assign it to ‘root->right’.
     
  7. Return ‘root’.

Dry Run 

  • The input is a vector of integers ‘preorder’ representing the preorder traversal of the input {15, 14, 18, 95, 47, 5, 479}.
     
  • The base case is not satisfied, since the start (0) is not greater than the end (6).
     
  • A new node root is created with the value of the first element of the preorder vector, which is 15.

dry run 1

  • Calculate the middle index as (start + end) / 2, which is (0 + 6) / 2 = 3.
     
  • Recursively call buildTree with the preorder, start = 1, and end = 3 to construct the left subtree of the root.
     
  • For this recursive call, a new Node object is created with data = preorder[1], which is 14. The function then calculates mid as (1 + 3) / 2, which is 2.

dry run 2

  • For the left subtree, create a new node with the data 14 and recursively call buildTree() with the start index as 2 and end index as 3. Since the start index is not greater than the end index, create a new node with data 18 and set its left and right pointers as NULL.
     
  • Similarly, for the right subtree, we create a new node with data 95 and set its left and right pointers as NULL.

dry run 3

  • Recursively call buildTree with preorder, start = 4, and end = 6 to construct the right subtree of the root.
     
  • For this recursive call, a new Node object is created with data = preorder[1], which is 47. The function then calculates mid as (4 + 6) / 2, which is 5.

dry run 4

  • For the left subtree, create a new node with the data 47 and recursively call buildTree() with the start index as 5 and end index as 6. Since the start index is not greater than the end index, create a new node with data 5 and set its left and right pointers as NULL. 
     
  • Similarly, for the right subtree, we create a new node with data 479 and set its left and right pointers as NULL.
     
  • Once all of the recursive calls have returned, return the root node, which recursively traverses the tree in inorder traversal.

dry run 5

  • Hence, the output comes [18, 14, 95, 15, 5, 47, 479].

Note: Make sure you are providing a perfect binary tree as input.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

// Node Class representing a node in a binary tree
class Node {
public:
    int data;     
    Node* left;   
    Node* right;  
    
    // Constructor for initializing a new node with given data
    Node(int val) {
        data = val;   
        left = right = NULL;  
    }
};

/*
    Takes the vector of preorder traversal, start and end 
    indices of the current subarray and return a pointer 
    to the root node of the constructed binary tree
*/
Node* buildTree(vector<int>& preorder, int start, int end) {
    
    /* 
        if the start index exceeds the end index,
        return NULL
    */
    if (start > end) {
        return NULL;  
    }

    /*
        Create a new node with the first element
        of the preorder traversal as the root of the
        current sub-tree
    */
    Node* root = new Node(preorder[start]);

    // Index of the middle element of the current subarray
    int mid = (start + end) / 2;

    /* 
        Recursively build the left and right
        subtrees of the current node 
    */
    root->left = buildTree(preorder, start + 1, mid);
    root->right = buildTree(preorder, mid + 1, end);

    /*
        Return the pointer to the root
        of the constructed binary tree 
    */
    return root;
}

// Print the inorder traversal of the binary tree
void print(Node* root) {
    
    // Base Case for the recursive function
    if (root == NULL) {
        return;  
    }

    // Traverse the left subtree
    print(root->left);

    // Print the data of the current node
    cout << root->data << " ";

    // Traverse the right subtree
    print(root->right);
}

// Driver Code
int main() {
    // Preorder traversal of a binary tree
    vector<int> preorder = {15, 14, 18, 95, 47, 5, 479};

    // Construct the perfect binary tree
    Node* root = buildTree(preorder, 0, preorder.size() - 1);

    // Print the inorder traversal of the constructed binary tree
    cout << "Inorder traversal of the tree: ";
    print(root);

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

output

Python Code

# Node Class representing a node in a binary tree
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

# Takes the vector of preorder traversal, start and end 
# indices of the current subarray and return a pointer 
# to the root node of the constructed binary tree

def buildTree(preorder, start, end):

    # if the start index exceeds the end index,
    # return NULL
    if start > end:
        return None
        
    # Create a new node with the first element
    # of the preorder traversal as the root of the
    # current sub-tree

    root = Node(preorder[start])

    # Index of the middle element of the current subarray
    mid = (start + end) // 2

    # Recursively build the left and right
    # subtrees of the current node 
    
    root.left = buildTree(preorder, start + 1, mid)
    root.right = buildTree(preorder, mid + 1, end)

    # Return the pointer to the root
    # of the constructed binary tree 
    return root

# Print the inorder traversal of the binary tree
def printInorder(root):
    # Base Case for the recursive function
    if root == None:
        return

    # Traverse the left subtree
    printInorder(root.left)
    
    # Print the data of the current node
    print(root.data, end=' ')
    
    # Traverse the right subtree
    printInorder(root.right)

# Preorder traversal of a binary tree
preorder = [15, 14, 18, 95, 47, 5, 479]

# Construct the perfect binary tree
root = buildTree(preorder, 0, len(preorder) - 1)

# Print the inorder traversal of the constructed binary tree
print("Inorder traversal of the tree:", end=' ')
printInorder(root)
You can also try this code with Online Python Compiler
Run Code


Output

out

Algorithm Complexity 

Time Complexity: O(N)

The time complexity is O(n) since we are traversing the complete preorder vector once and constructing the binary tree, Therefore, the time complexity is O(N).

Space Complexity: O(N)

As we are using ‘N’ extra space to store the binary tree, therefore, the overall space complexity will be O(N).

Must Read Recursive Binary Search.

Frequently Asked Questions

What is the perfect binary tree?

The binary tree in which a root has either 2 or 0 children is known as the perfect binary tree.

What is a subtree in a binary tree?

A subtree in a binary tree is a smaller tree that is formed by selecting a node and all of its descendants in the original tree.

What are the data members of a TreeNode class?

TreeNode class consists of 3 data members, namely data, a pointer to the left child, and a pointer to the right child.

What do you mean by preorder traversal?

Preorder traversal visits the root node first, followed by its left and right subtrees.

What do you mean by Inorder traversal?

Inorder traversal, visits the left subtree, then the root, and finally the right subtree.

Conclusion

In this blog, we learned how to construct a perfect binary tree from a preorder traversal. We have implemented the problem in C++ and Python programming languages.

For more Tree data structure articles, you can refer following links:

Recommended problems -

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass