Construct a full binary tree from a preorder and postorder sequence
A full binary tree is a tree in which every node has either 0 or 2 children. Write an efficient algorithm to construct a full binary tree from a given preorder and postorder sequence.
For example,
Preorder traversal : { 1, 2, 4, 5, 3, 6, 8, 9, 7 }
Postorder traversal: { 4, 5, 2, 8, 9, 6, 7, 3, 1 }
Output: Following full binary tree
We can construct a unique binary tree from inorder and preorder sequences and the inorder and postorder sequences. But preorder and postorder sequences don’t provide enough information to create a unique binary tree. Several binary trees can be constructed due to ambiguity.
For example, consider the following skewed trees:
/ \
b b
/ \
c c
/ \
d d
For both above trees, the preorder and postorder traversal result in the same sequence of numbers:
postorder : { d, c, b, a }
Therefore, it is impossible to construct a unique binary tree with preorder and postorder sequences. However, a unique full binary tree can easily be constructed with them. To illustrate, consider the following preorder and postorder sequence:
postorder : { 4, 5, 2, 8, 9, 6, 7, 3, 1 }
We know that the root is the first element in the preorder sequence and the last element in the postorder sequence. Therefore, the root node is 1. Then locate the next element in the preorder sequence, which must be the left child of the root node. In this case, the left child is 2. Now since 2 is the root node of the left subtree, all nodes before 2 in the postorder sequence must be present in the left subtree of the root node, i.e., {4, 5, 2} and all the nodes after 2 (except the last) must be present in the right subtree, i.e., {8, 9, 6, 7, 3}. Now the problem is reduced to building the left and right subtrees and linking them to the root node.
Postorder : {4, 5, 2}
Preorder : {2, 4, 5}
Right subtree:
Postorder : {8, 9, 6, 7, 3}
Preorder : {3, 6, 8, 9, 7}
The idea is to recursively follow the above approach until the complete tree is constructed. This is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to perform inorder traversal on a given binary tree void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << ' '; inorder(root->right); } // A recursive function to construct a full binary tree from the given preorder // and postorder sequence Node* buildTree(auto &preorder, int &pIndex, int start, int end, auto &map) { // Consider the next item from the given preorder sequence. // This item would be the root node of the subtree formed by // the postorder[start, end] Node* root = new Node(preorder[pIndex]); // increment `pIndex` pIndex++; // return if all keys are processed if (pIndex == preorder.size()) { return root; } // find the next key index in the postorder sequence to determine the // boundary of the left and right subtree of the current root node int index = map[preorder[pIndex]]; // fill the left and right subtree together if (start <= index && index + 1 <= end - 1) { // build the left subtree root->left = buildTree(preorder, pIndex, start, index, map); // build the right subtree root->right = buildTree(preorder, pIndex, index + 1, end - 1, map); } return root; } // Construct a full binary tree from preorder and postorder sequence Node* buildTree(auto const &preorder, auto const &postorder) { // base case if (postorder.size() == 0) { return nullptr; } // map is used to efficiently find the index of any element in the given // postorder sequence unordered_map<int, int> map; for (int i = 0; i < postorder.size(); i++) { map[postorder[i]] = i; } // `pIndex` stores the index of the next node in the preorder sequence int pIndex = 0; // set range [start, end] for subtree formed by postorder sequence int start = 0; int end = preorder.size() - 1; // construct the binary tree and return it return buildTree(preorder, pIndex, start, end, map); } int main() { vector<int> preorder = { 1, 2, 4, 5, 3, 6, 8, 9, 7 }; vector<int> postorder = { 4, 5, 2, 8, 9, 6, 7, 3, 1 }; Node* root = buildTree(preorder, postorder); cout << "Inorder traversal is "; inorder(root); return 0; } |
Output:
Inorder traversal is 4 2 5 1 8 6 9 3 7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
import java.util.HashMap; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger; // A class to store a binary tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to perform inorder traversal on a given binary tree public static void inorder(Node root) { if (root == null) { return; } inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } // A recursive function to construct a full binary tree from the given preorder // and postorder sequence public static Node buildTree(int[] preorder, AtomicInteger pIndex, int start, int end, Map<Integer, Integer> map) { // Consider the next item from the given preorder sequence. // This item would be the root node of the subtree formed by // the `postorder[start, end]` and increment `pIndex` Node root = new Node(preorder[pIndex.getAndIncrement()]); // return if all keys are processed if (pIndex.get() == preorder.length) { return root; } // find the next key index in the postorder sequence to determine the // boundary of the left and right subtree of the current root node int index = map.get(preorder[pIndex.get()]); // fill the left and right subtree together if (start <= index && index + 1 <= end - 1) { // build the left subtree root.left = buildTree(preorder, pIndex, start, index, map); // build the right subtree root.right = buildTree(preorder, pIndex, index + 1, end - 1, map); } return root; } // Construct a full binary tree from preorder and postorder sequence public static Node buildTree(int[] preorder, int[] postorder) { // base case if (postorder.length == 0) { return null; } // map is used to efficiently find the index of any element in the given // postorder sequence Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < postorder.length; i++) { map.put(postorder[i], i); } // `pIndex` stores the index of the next node in the preorder sequence AtomicInteger pIndex = new AtomicInteger(0); // set range [start, end] for subtree formed by postorder sequence int start = 0; int end = preorder.length - 1; // construct the binary tree and return it return buildTree(preorder, pIndex, start, end, map); } public static void main(String[] args) { int[] preorder = { 1, 2, 4, 5, 3, 6, 8, 9, 7 }; int[] postorder = { 4, 5, 2, 8, 9, 6, 7, 3, 1 }; Node root = buildTree(preorder, postorder); System.out.print("Inorder traversal is "); inorder(root); } } |
Output:
Inorder traversal is 4 2 5 1 8 6 9 3 7
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
# A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to perform inorder traversal on a given binary tree def inorder(root): if root is None: return inorder(root.left) print(root.data, end=' ') inorder(root.right) # A recursive function to construct a full binary tree from the given preorder # and postorder sequence def buildTree(preorder, pIndex, start, end, d): # Consider the next item from the given preorder sequence. # This item would be the root node of the subtree formed by # the `postorder[start, end]` and increment `pIndex` root = Node(preorder[pIndex]) pIndex = pIndex + 1 # return if all keys are processed if pIndex == len(preorder): return root, pIndex # find the next key index in the postorder sequence to determine the # boundary of the left and right subtree of the current root node index = d.get(preorder[pIndex]) # fill the left and right subtree together if start <= index and index + 1 <= end - 1: # build the left subtree root.left, pIndex = buildTree(preorder, pIndex, start, index, d) # build the right subtree root.right, pIndex = buildTree(preorder, pIndex, index + 1, end - 1, d) return root, pIndex # Construct a full binary tree from preorder and postorder sequence def buildBinaryTree(preorder, postorder): # base case if not preorder: return # dictionary is used to efficiently find the index of any element in the given # postorder sequence d = {} for i, e in enumerate(postorder): d[e] = i # `pIndex` stores the index of the next node in the preorder sequence pIndex = 0 # set range [start, end] for subtree formed by postorder sequence start = 0 end = len(preorder) - 1 # construct the binary tree and return it return buildTree(preorder, pIndex, start, end, d)[0] if __name__ == '__main__': preorder = [1, 2, 4, 5, 3, 6, 8, 9, 7] postorder = [4, 5, 2, 8, 9, 6, 7, 3, 1] root = buildBinaryTree(preorder, postorder) print('Inorder traversal is ', end='') inorder(root) |
Output:
Inorder traversal is 4 2 5 1 8 6 9 3 7
Note that the above algorithm will ensure a unique binary tree only when all keys in the given preorder/postorder sequence are distinct. For example, two full binary trees exist for following preorder and postorder sequences whose node keys are not distinct:
The postorder traversal is { 1, 1, 1, 1, 0 }
0
/ \
1 1
/ \
1 1
0
/ \
1 1
/ \
1 1
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of nodes in the binary tree.
Find preorder traversal of a binary tree from its inorder and postorder sequence
Find postorder traversal of a binary tree from its inorder and preorder sequence
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)