CODEWITHSUNDEEP
binary-search-treepermutationpreorder
HelpMe
HelpMe

Reputation: 1

permutations of bst , given preorder array

Given a Preorder array of a Binary Search Tree how many other permutations of the given binary search tree will form the same BST as the given preorder.

Upvotes: -2

Views: 96

Answers (1)

trincot
trincot

Reputation: 351308

First of a all: a value in a preorder sequence can never become an ancestor node of a node that has a value that occurred earlier in that sequence (this would be a contradiction with "preorder"). Any next value in the sequence (except the first) represents a child node of an earlier value's node. So values that are added to a tree are always leaves at the moment they are added -- never internal nodes.

The preorder sequence starts with the root, so any BST that it represents, must have it as root.

Any next value must be added as a leaf. So for the second value in the sequence there are 2 potential positions for it. For the 3rd, 3, for the 4th 4, ...etc. However, since the partial tree formed by the first k values must be a BST, there is only one of these positions for the unique (k+1)th value that is in line with the BST requirement, so there is never a choice between multiple alternatives.

By induction that means that only one BST can be formed from a preorder sequence of unique values.

Upvotes: 0

Related Questions