Find all possible binary trees with given Inorder Traversal - GeeksforGeeks
Given an array that represents Inorder Traversal, find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Related: Construct all possible BSTs for keys 1 to N
Read full article from Find all possible binary trees with given Inorder Traversal - GeeksforGeeks
Given an array that represents Inorder Traversal, find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Let given inorder traversal be in[]. In the given traversal, all nodes in left subtree of in[i] must appear before it and in right subtree must appear after it. So when we consider in[i] as root, all elements from in[0] to in[i-1] will be in left subtree and in[i+1] to n-1 will be in right subtree. If in[0] to in[i-1] can form xdifferent trees and in[i+1] to in[n-1] can from y different trees then we will have x*y total trees when in[i] as root. So we simply iterate from 0 to n-1 for root. For every node in[i], recursively find different left and right subtrees. If we take a closer look, we can notice that the count is basically n’th Catalan number. We have discussed different approaches to find n’th Catalan number here.
The idea is to maintain a list of roots of all Binary Trees. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.
1) Initialize list of Binary Trees as empty. 2) For every element in[i] where i varies from 0 to n-1, do following ......a) Create a new node with key as 'arr[i]', let this node be 'node' ......b) Recursively construct list of all left subtrees. ......c) Recursively construct list of all right subtrees. 3) Iterate for all left subtrees a) For current leftsubtree, iterate for all right subtrees Add current left and right subtrees to 'node' and add 'node' to list.
class
Node {
int
data;
Node left, right;
public
Node(
int
item) {
data = item;
left =
null
;
right =
null
;
}
}
/* Class to print Level Order Traversal */
class
BinaryTree {
Node root;
// A utility function to do preorder traversal of BST
void
preOrder(Node node) {
if
(node !=
null
) {
System.out.print(node.data +
" "
);
preOrder(node.left);
preOrder(node.right);
}
}
// Function for constructing all possible trees with
// given inorder traversal stored in an array from
// arr[start] to arr[end]. This function returns a
// vector of trees.
Vector<Node> getTrees(
int
arr[],
int
start,
int
end) {
// List to store all possible trees
Vector<Node> trees=
new
Vector<Node>();
/* if start > end then subtree will be empty so
returning NULL in the list */
if
(start > end) {
trees.add(
null
);
return
trees;
}
/* Iterating through all values from start to end
for constructing left and right subtree
recursively */
for
(
int
i = start; i <= end; i++) {
/* Constructing left subtree */
Vector<Node> ltrees = getTrees(arr, start, i -
1
);
/* Constructing right subtree */
Vector<Node> rtrees = getTrees(arr, i +
1
, end);
/* Now looping through all left and right subtrees
and connecting them to ith root below */
for
(
int
j =
0
; j < ltrees.size(); j++) {
for
(
int
k =
0
; k < rtrees.size(); k++) {
// Making arr[i] as root
Node node =
new
Node(arr[i]);
// Connecting left subtree
node.left = ltrees.get(j);
// Connecting right subtree
node.right = rtrees.get(k);
// Adding this tree to list
trees.add(node);
}
}
}
return
trees;
}
class
Node:
# Utility to create a new node
def
__init__(
self
, item):
self
.key
=
item
self
.left
=
None
self
.right
=
None
# A utility function to do preorder traversal of BST
def
preorder(root):
if
root
is
not
None
:
print
root.key,
preorder(root.left)
preorder(root.right)
# Function for constructing all possible trees with
# given inorder traversal stored in an array from
# arr[start] to arr[end]. This function returns a
# vector of trees.
def
getTrees(arr , start , end):
# List to store all possible trees
trees
=
[]
""" if start > end then subtree will be empty so
returning NULL in the list """
if
start > end :
trees.append(
None
)
return
trees
""" Iterating through all values from start to end
for constructing left and right subtree
recursively """
for
i
in
range
(start , end
+
1
):
# Constructing left subtree
ltrees
=
getTrees(arr , start , i
-
1
)
# Constructing right subtree
rtrees
=
getTrees(arr , i
+
1
, end)
""" Looping through all left and right subtrees
and connecting to ith root below"""
for
j
in
ltrees :
for
k
in
rtrees :
# Making arr[i] as root
node
=
Node(arr[i])
# Connecting left subtree
node.left
=
j
# Connecting right subtree
node.right
=
k
# Adding this tree to list
trees.append(node)
return
trees
# Driver program to test above function
inp
=
[
4
,
5
,
7
]
n
=
len
(inp)
trees
=
getTrees(inp ,
0
, n
-
1
)
print
"Preorder traversals of different possible\
Binary Trees are "
for
i
in
trees :
preorder(i);
print
""
Related: Construct all possible BSTs for keys 1 to N
Read full article from Find all possible binary trees with given Inorder Traversal - GeeksforGeeks