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,
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]
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
-
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.
-
If ‘start > end’, return NULL.
-
Create a new node ‘root’ with the value ‘preorder[start]’.
-
Compute the middle index `mid` as ‘(start + end) / 2’.
-
Recursively build the left subtree using ‘buildTree(preorder, start + 1, mid)’ and assign it to ‘root->left’.
-
Recursively build the right subtree using ‘buildTree(preorder, mid + 1, end)’ and assign it to ‘root->right’.
- 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.
-
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.
-
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.
-
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.
-
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.
- 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;
}
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)
Output
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.