When we are creating trees by computing the cartesian product of all possible left subtrees and right subtrees, aren’t some subtrees being shared ? Do we need to clone the tree so that each BST won’t be affected by another ?
Yes there would be shared subtrees but I don’t think their bst structure will be messed up. It’s just that the root of a subtree will be the child that can be accessed by multiple parent nodes.
1 Like