Construct A Perfect Binary Tree From A Preorder Traversal

Harsh Goyal
Last Updated: May 13, 2022

Introduction  

This blog will discuss the approach to solve the Construct a perfect binary tree from a preorder traversal. Before jumping into the problem to get the Sum of the distance of all Nodes from a given node in a binary tree, let’s first understand what is a binary tree.

Revisiting Binary tree

A binary Tree is a type of tree in which a node can have at most two children, commonly known as left and right child of the node. Its class has three data members which are as follows:-  

  1. Data 
  2. Left Node pointer
  3. Right Node pointer

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

Problem Statement

In this problem, we need to find the sum of the distance of each node from a given node.

Sample Example

Preorder:- [15, 10, 20, 8, 12, 18, 25]

Output:- 

Approach

As we know that in a preorder traversal of a binary tree comprises of a root first and then the preorder traversal of the left child’s subtree, and then the preorder traversal of the right child’s subtree of that particular root. This concludes that in the perfect binary tree, the total count of the nodes in both the subtrees of the root will be the same. The first element will always be the root’s data in the preorder traversal.

Algorithm 

Step 1. Create a function ‘getResult()’ that will accept 2 parameters, i.e., one vector of integer ‘preorder’ and second is the size of that vector. 

Step 2. Create a function ‘getResult_helper’ that will accept 3 parameters, i.e., one vector of integer ‘preorder’ and second is the ‘preStart’ which is the start index and third is the ‘preEnd’ which is the end index for the vector.

Step 3. Call ‘getResult_helper’ from the ‘getResult’ function and pass 0, ‘N - 1’, and ‘preorder’ as the parameters.

Step 4. In the ‘getResult_helper’ function, if the value of ‘preStart’ is greater than ‘preEnd’ then return null.

Step 5. As we know that it is the preorder, which means the first element will the root, therefore, make the element at the ‘preStart’ index of ‘preorder’ as root using the ‘push’ function.

Step 6. If ‘preStart’ and ‘preEnd’ are equal, then return the ‘root’.

Step 7. Update the value of ‘leftPreStart’, ‘rightPreStart’, ‘leftPreEnd’, and, ‘rightPreEnd’ as shown in the code.

Step 8. Make a recursive call to ‘getResult_helper’ and pass ‘leftPreStart’, ‘leftPreEnd’ and ‘preorder’ and assign the returned value to the left child of the ‘root’.

Step 9. Make a recursive call to ‘getResult_helper’ and pass ‘rightPreStart’, ‘rightPreEnd’ and ‘preorder’ and assign the returned value to the right child of the ‘root’.

Step 10. Return root.

 

Implementation in C++

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

// Node Class
class Node
{
   public:
   int data;
   Node *left, *right;

   Node(int val)
   {
       data = val;
       left = right = NULL;
   }
};

// Function to create a new node with
// the value val
Node* push(int val)
{
   Node* newNode = new Node(val);
   newNode -> data = val;
   newNode -> left = newNode -> right = NULL;

   // Return the new node
   return newNode;
}

// construct the tree
Node* getResult_helper(int preStart,int preEnd, vector<int> preorder)
{
   // If preStart > preEnd return NULL
   if (preStart > preEnd)
   {
       return NULL;
   }

   // Initialize root as pre[preStart]
   Node* root = push(preorder[preStart]);
   ;

   // If the only node is left,
   // then return node
   if (preStart == preEnd)
   {
       return root;
   }

   // Parameters for further recursion
   int leftPreStart = preStart + 1;
   int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2;
   int leftPreEnd = rightPreStart - 1;
   int rightPreEnd = preEnd;

   // Construct the subtree
   root->left = getResult_helper(leftPreStart, leftPreEnd, preorder);

   root->right = getResult_helper(rightPreStart, rightPreEnd, preorder);

   // Return the construct binary tree's root
   return root;
}

// Function to build Perfect Binary Tree
Node* getResult(vector<int> preorder, int N)
{
   return getResult_helper(0, N - 1, preorder);
}

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

   // Left subtree
   print(root->left);

   // Data of the root
   cout << root -> data << ", ";

   // Right subtree
   print(root -> right);
}

// Driver Code
int main()
{
   vector<int> preorder = { 15, 14, 18, 95, 47, 5, 479};
   int N = preorder.size();

   // Construct the perfect binary tree
   Node* root = getResult(preorder, N);

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

   return 0;
}

 

Output:

Inorder traversal of the tree:- 18, 14, 95, 47, 15, 479, 5

 

Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, we are traversing the complete preorder vector once and constructing the binary tree and using push function and other recursive calls which will take at max ‘N’ computational time, therefore, the overall 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).

Frequently asked questions

Q1) What is the perfect binary tree?

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

 

Q2) What is a Subtree in a binary tree?

Ans. In a Binary tree, a subtree of a node is recognized as another binary tree whose root node is that particular node. In a Binary tree, there are two types of subtrees

  • Left Subtree
  • Right Subtree

Note:- The value of subtree can be Null also.

 

Q3) What are the data members of a TreeNode class?

Ans. TreeNode class consists of 3 data members, 

  • Data 
  • Pointer to Left child
  • Pointer to Right child.

Key takeaways

In this article, we discussed the What is Construct a perfect binary tree from a preorder traversal, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think