PROBLEM LINK:
Author: Prasad
Tester: Naresh
Editorialist: Prasad
DIFFICULTY:
MEDIUM
PREREQUISITES:
BST Properties
PROBLEM:
Given a Binary Search Tree of size n rooted at R, which contains all numbers in the range [1,n] (Both inclusive).
Find the different number of permutations of first n natural numbers which are compatible with given Binary Search Tree.
A permutation is said to be compatible with given BST if it constructs the same BST when nodes are inserted to an empty BST according to the permutation ordering.
EXPLANATION:
You are given a structure of a BST containing 1 to n numbers(Both inclusive). We know that the same BST structure can be obtained even if the input order is different. This is because of the property of BST that The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
So different permutations of the nodes in left and right subtrees can be merged to form the given tree structure.
At root, we have to find number of ways to construct its left subtree, number of ways to construct its right subtree and then the number of ways to interleave two ordered sequences of left and right subtree.
Let F(root) gives the desired answer.
Let subtree rooted at root contains n nodes, its left subtree contains x nodes and right subtree contains y nodes (x+y+1 = n).
F(root) = F(root->left) * F(root->right) * (x+y)Cx;
F(leafnode) = 1;
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.