Find all possible binary trees having the same inorder traversal
Given an inorder sequence of a binary tree, find all possible binary trees having that same inorder traversal.
For example, there are 5 binary trees with inorder traversal [1, 2, 3], as shown below:
1 1 2 3 3
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
We know that, in the inorder traversal on a given binary tree, all nodes in the left subtree of the root must appear before the root node and all nodes in the right subtree appear after the root node. Therefore, for inorder sequence in[0, n-1] with i'th element as root, all elements in range in[0, i-1] will be part of the left subtree, and all elements in range in[i+1, n-1] will be part of the right subtree.
The idea is to iterate over the given inorder sequence and consider each element as the root of the binary tree. Then recursively construct all possible left and right subtrees of the root. Finally, create a tree for each pair of left and right subtree, and add that tree to the output list.
The algorithm can be implemented as follows 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 |
#include <iostream> #include <vector> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data, Node *left, Node *right) { this->data = data; this->left = left; this->right = right; } }; // Utility function to perform preorder traversal on a given binary tree void preorder(Node* root) { if (root == nullptr) { return; } cout << root->data << ' '; preorder(root->left); preorder(root->right); } // Recursive function to return a list of tree pointers of all possible // binary trees having the same inorder sequence as `in[start, end]` vector<Node*> generateBinaryTrees(vector<int> &in, int start, int end) { // create an empty list to store the root of the constructed binary trees vector<Node*> trees; // base case if (start > end) { trees.push_back(nullptr); return trees; } // consider each element in the inorder sequence as the root for (int i = start; i <= end; i++) { // recursively find all possible left subtrees for root `i` vector<Node*> left_subtrees = generateBinaryTrees(in, start, i - 1); // recursively find all possible right subtrees for root `i` vector<Node*> right_subtrees = generateBinaryTrees(in, i + 1, end); // do for each combination of left and right subtrees for (Node* l: left_subtrees) { for (Node* r: right_subtrees) { // construct a binary tree with i'th element as the root and whose // left and right children point to `l` and `r`, respectively Node* tree = new Node(in[i], l, r); // add this tree to the output list trees.push_back(tree); } } } return trees; } int main() { vector<int> inorder = { 1, 2, 3 }; vector<Node*> trees = generateBinaryTrees(inorder, 0, inorder.size() - 1); cout << "Total binary trees are " << trees.size() << "\n\n"; cout << "Preorder traversal for each tree:\n"; for (Node* tree: trees) { preorder(tree); cout << endl; } return 0; } |
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 |
import java.util.ArrayList; import java.util.List; // Data structure to store a binary tree node class Node { int data; Node left, right; Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } class Main { // Utility function to perform preorder traversal on a given binary tree public static void preorder(Node root) { if (root == null) { return; } System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } // Recursive function to return a list of tree pointers of all possible // binary trees having the same inorder sequence as `in[start, end]` public static List<Node> generateBinaryTrees(int[] in, int start, int end) { // create an empty list to store the root of the constructed binary trees List<Node> trees = new ArrayList<>(); // base case if (start > end) { trees.add(null); return trees; } // consider each element in the inorder sequence as the root for (int i = start; i <= end; i++) { // recursively find all possible left subtrees for root `i` List<Node> left_subtrees = generateBinaryTrees(in, start, i - 1); // recursively find all possible right subtrees for root `i` List<Node> right_subtrees = generateBinaryTrees(in, i + 1, end); // do for each combination of left and right subtrees for (Node l: left_subtrees) { for (Node r: right_subtrees) { // construct a binary tree with i'th element as the root and whose // left and right children point to `l` and `r`, respectively Node tree = new Node(in[i], l, r); // add this tree to the output list trees.add(tree); } } } return trees; } public static void main(String[] args) { int[] inorder = { 1, 2, 3 }; List<Node> trees = generateBinaryTrees(inorder, 0, inorder.length - 1); System.out.println("Total binary trees are " + trees.size()); System.out.println("Preorder traversal for each tree:"); for (Node tree: trees) { preorder(tree); System.out.println(); } } } |
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 |
# Data structure 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 # Utility function to perform preorder traversal on a given binary tree def preorder(root): if root is None: return print(root.data, end=' ') preorder(root.left) preorder(root.right) # Recursive function to return a list of tree pointers of all possible # binary trees having the same inorder sequence as `in[start, end]` def generateBinaryTrees(inorder, start, end): # create an empty list to store the root of the constructed binary trees trees = [] # base case if start > end: trees.append(None) return trees # consider each element in the inorder sequence as the root for i in range(start, end + 1): # recursively find all possible left subtrees for root `i` left_subtrees = generateBinaryTrees(inorder, start, i - 1) # recursively find all possible right subtrees for root `i` right_subtrees = generateBinaryTrees(inorder, i + 1, end) # do for each combination of left and right subtrees for l in left_subtrees: for r in right_subtrees: # construct a binary tree with i'th element as the root and whose # left and right children point to `l` and `r`, respectively tree = Node(inorder[i], l, r) # add this tree to the output list trees.append(tree) return trees if __name__ == '__main__': inorder = [1, 2, 3] trees = generateBinaryTrees(inorder, 0, len(inorder) - 1) print("Total binary trees are", len(trees)) print("Preorder traversal for each tree:") for tree in trees: preorder(tree) print() |
Output:
Total binary trees are 5
Preorder traversal for each tree:
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
Total binary trees are 5
Preorder traversal for each tree:
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
Also See:
Find postorder traversal of a binary tree from its inorder and preorder sequence
Find preorder traversal of a binary tree from its inorder and postorder 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 :)